10

これは私の最初のスタックオーバーフローの質問なので、優しくしてください。これがすでに殴打されている場合は、事前に謝罪します... NP でいくつかのスレッドを読みましたが、質問に対する興味をそそる答えが見つかりませんでした (どちらかといえば、いくつかの新しいものを思いつきました)。簡単に言うと:

  1. 決定可能だが NP ではない決定問題はありますか?
  2. もしそうなら、解決を求める問題は同等の決定問題より難しいですか?

私の疑惑は、最初の質問に対する答えは圧倒的に「はい」であり、2番目の質問に対する答えは圧倒的に「いいえ」であるということです.

最初のケースでは、問題の例として、「集合 S、S の部分集合 T、およびドメイン 2^S の関数 f が与えられた場合、T が f を最大化するかどうかを判断する」というものがあります。一般的な S、T、および f の場合、S のすべてのサブセット X について f(X) をチェックしないと、これを検証することさえできませんよね?

2 番目のケースでは...まあ、これは勘に過ぎないと認めます。何らかの理由で、答えに 1 ビット (決定問題の場合) が含まれているか、任意の (有限の) ビット数が含まれているかは問題ではないように思われます。 「回答」の一部としてTMが停止した後、テープに残された記号。

編集：実際、質問があります...関数の問題が決定の問題よりも「難しくない」ことをあなたの構造はどの程度正確に示していますか? どちらかといえば、決定問題よりも関数の問題に答える方が簡単ではないことを示しました...これは些細なことです。ずさんなやり方で質問した私のせいかもしれません。

NP に TM T1 があり、変数 X と (議論のために) 固定 P について「X は問題 P の解決策か」という問題を解決する場合、T1 が停止するすべての場所で停止する TM T2 が NP に存在することが保証されますか? 、どこでも「停止受け入れ」状態で終了し、テープに X のバイナリ表現などを残しますか?

4

1 に答える 1

16

（1）はい、決定可能であるがNPにはない決定問題があります。NP⊊NEXPという時間階層定理の結果であるため、 NEXPハード問題はNPにはありません。正規の例は次の問題です。

非決定性チューリングマシンMとバイナリで記述された整数nが与えられた場合、 Mは最大nステップ で空の文字列を受け入れますか？

この問題は確かに決定可能です（長さnのMのすべての計算パスをシミュレートし、受け入れられるものがある場合はそれをシミュレートします）。

さらに多くのNEXP完全な問題については、cstheory.stackexchange.comでこの質問を参照してください。そしてもちろん、NEXPの外には決定問題があります：確かに、それらの全体の指数階層...

（2）2番目の質問に対する答えはノーです。関数問題は決定問題よりも難しいことではありません。（「より難しくない」という特定の技術的な意味で。）出力Nを要求する関数の問題があるとします。次に、入力kを受け取り、 Nのk番目のビットが1であるかどうかを尋ねる決定問題があります。答えのすべてのビットについてこの決定問題を解くと、完了です。

たとえば、FSAT（ブール式への満足のいく代入を見つける問題）は、多項式時間でSAT（ブール式に満足のいく代入があるかどうかを判断する問題）に短縮できます。SATを解くことができ、式φの満足のいく割り当てを見つけるように求められたとします。式φの最初の変数xを検討し、SATにx∧φが充足可能かどうかを尋ねます。そうである場合、 xが真であるφに対して満足のいく割り当てがなければなりません。そうでない場合、およびφが充足可能である場合、xが偽であるφに対して満足のいく割り当てがなければなりません。2番目の変数yを続行し、xかどうかを尋ねます∧<i>y∧φ（または最初の質問への回答によると、¬x∧<i>y∧φ）は充足可能です。数式の各変数についても同様です。

[この例について重要な警告を追加する必要があります。ここで、SATとFSATは「自然に」関連しています。どちらも同じ種類のこと、つまり数式への割り当てを満たすことに関係しています。しかし、検索は一般的に決定に還元できるという私の議論では、出力のk番目のビットについて非常に人工的な決定問題を使用しました。したがって、検索は決定に還元されますが、必ずしも自然に対応する決定問題に還元されるわけではありません。特に、BellareとGoldwasserは、検索をそれほど減らすことができない場合があることを示しました。]

于 2011-07-15T20:32:41.300 に答える