computation-theory - αの因数分解の問題がNPにあることを証明する

Question

計算理論をブラッシュアップしようとしていますが、これに対する解決策がわかりません：

Prove that the problem of factoring α is in NP.

NP問題の発見とα因数分解の問題の縮小の発見に関係しているのではないかと感じています。

Answer 1

これは実際には簡単です。乗算はPにあります。NPは「すべての可能な多項式サイズの解を並列にチェックする」と同じです。アルファが長さnのビット文字列としてエンコードされている場合、因子の全長は最大でn+cです。

そうではないのは「NP完全」です。任意のNP問題を因数分解に変える方法はありません。

Answer 2

Pの問題：は問題であり、多項式時間で決定性チューリングマシンによって計算可能です 。NPの問題：は問題であり、これは決定性チューリングマシンによって多項式的に非常に忠実です。

NPでは、非決定論を使用しているため、計算ツリーの1つのブランチのみを受け入れる必要があります（「すべての」可能性を「同時に」試行します）。ポリノミカ的に非常に忠実であるということは、入力された単語（wとしましょう）の解決策である証明書（cとしましょう）を持っていることを意味します。証明書は、入力の長さを考慮した多項式の長さである必要があります。私たちの仕事は、証明書が解決策であるかどうかを確認することだけです。たとえば、SAT（満足度の問題）では、証明書は正しい割り当てです（これは非決定論的に推測されます）。

したがって、問題がNPにあることを証明します。ペア（w、c）を検証するDTMが存在します。ここで、wは入力番号であり、cはその因子です。cの因子を乗算し、それをwと比較する非常に優れたものを構築する必要があります。