私はあなたが検証証明書を与えることができないことを知っています. しかし、私は考えていたのですが、SAT を決定する NDTM に入力を与えてから、答えを逆にできないのはなぜでしょうか? 欠陥はどこにありますか？
質問する
3044 次
1 に答える
5
SAT の補数が NP にあるかどうかは実際にはわかっていません。P = NP の場合、すべての P 言語は補数の下で閉じているため、SAT の補数は NP でなければなりません (P にあるため)。それ以外の場合、SAT の補数が NP にない場合は、同様のロジックを使用して P ≠ NP になります。
SAT の補数は (ガベージの不正な文字列を無視して) 満たされない命題式で構成されているため、SAT の補数は NP に含まれていないことが疑われます。数式が真に評価されないかどうかを判断するのに役立つ非決定論的に推測できる情報は不明ですが、SAT の場合、数式が実際に充足可能かどうかを確認するために、満足のいく代入を非確定論的に推測するのは簡単です。
あなたの推論のエラーについては、NTMは、計算の受け入れブランチがある場合に受け入れます。すべての「受け入れ」を「拒否」に反転すると、計算の全体的な結果は反転しません。計算結果を反転するには、少なくとも 1 つのブランチが受け入れる場合とは対照的に、すべてのブランチが受け入れる場合に補完された NTM を受け入れる必要があります。
お役に立てれば！
于 2013-10-21T01:34:32.767 に答える