チューリングマシンの停止確率と 3 CNF SAT の間に関係はありますか? 私はこれを見つけることができません アルゴリズムの本 それらの間の関係は何ですか?
質問する
627 次
3 に答える
4
停止問題は難しいです。
3-SAT は NP 完全ですが、停止問題は一般的なケースでは決定できません。つまり、チューリング マシン上で一般的な停止問題を解決するアルゴリズムを作成することは不可能です。
その理由についての直感は、停止問題が、チューリング マシンで解ける決定問題と同じくらい難しくなる可能性があるということです。答えが見つかった場合に停止する難しい問題のソルバーを作成し、そのソルバーが停止するかどうかを尋ねることができます。
于 2013-09-30T09:41:20.290 に答える
2
停止問題は、チューリング マシンが無限の時間を認識できる言語についてです。これは厳密に論理的な問題です。
3SAT 問題は、問題を解決するために必要な操作の数、つまり、どれくらいの時間が必要かという問題です。遅いアルゴリズムが存在することが知られているため、これは速いアルゴリズムを見つけることに関する問題です。
于 2013-09-30T09:50:52.690 に答える