R \ Pの問題（例題を探す）

私は計算可能性の理論を研究していますが、私は明らかに解決できる問題を探していますが、多項式時間ではありません。R Pの問題（例題を探す）

私はすべての種類の例のことを考えてみましたが、彼らは多項式時間で解くことができない理由は明らかではなかった...

2012-02-11 Belgi

http://en.wikipedia.org/wiki/Computational_complexity_theory#Problems_in_NP_not_known_to_be_in_P_or_NP-complete –

... – Belgi

誰であればP = NPは知りません!! –

The travelling sales man problem。 P = NPそれは例はない場合

2012-02-11 09:13:49

ありがとう、私は何かもっとシンプルな、P – Belgi

にはっきりしていない何かを探していますそれは非常に簡単です。可能なすべてのパスを確認する必要があります。ノードを追加すると、検索スペースが指数関数的に増加します。最短経路とは異なり、ショートカットはありません。最短経路で検索スペースを刈ることができます。 –

答えて