長文失礼．

>>292
最初に「経路を求める問題だから NP に属してないでしょ？」
という指摘について．多分これは日本 Wikipedia の
> なお NP はクラス P 同様、判定問題のクラスであり
> yes/no で答えることの出来ない問題は NP には属さない。
という記述を参考にしたものだと思うが，微妙なところ．

判定問題以外の問題の計算量を考えるとき，特に証拠として
もとの問題の解が求まるような場合は，その判定問題版を考えて
NP などと主張するのが普通．今回も基本的にはそのノリで
NP と主張している．
しかし，わざわざ判定問題に落とすのが面倒だという話があって，
問題のクラスを一般化した FP や FNP という計算量のクラスがある．
適切な判定問題に落として P/NP という場合は 大体 FP/FNP に
なっており，整合性がある．そこで，これらを適当に混同し，
判定問題以外について NP と主張するのはそれほど特殊なことではない．