0

グラフにハミルトニアン パスがあるかどうかを調べるには、多項式時間では計算できないと言われました。多項式時間で解けると仮定しましょう。これを証明するにはどうすればよいでしょうか? NP困難問題だから無理？

4

1 に答える 1

0

ハミルトニアンパス問題はNP 完全です。多項式時間で解くことが不可能であることは
誰も証明していませんが、そのような解が存在する可能性は非常に低いです。たまたま見つけた場合、これは P=NP を証明したことを意味し、Clay Math Institute は文字通り百万ドルを授与します :)

于 2013-11-28T02:23:02.163 に答える