αを考慮する問題がNPにあることを証明する

Question

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

Prove that the problem of factoring α is in NP.

NPの問題を見つけて、αを考慮するという問題の減少を見つけることに関連していると感じています。

Answer 1

これは実際には簡単です。乗算はPにあります。NPは「可能なすべての多項式サイズのソリューションを並行してチェックする」と同じです。アルファが長さnビットストリングとしてエンコードされている場合、因子の合計長はせいぜいn + cです。

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

Answer 2

pの問題 ：問題であり、それは多項式時間に決定論的なチューリングマシンによって計算可能ですNPの問題 ：問題ですが、Thasは決定論的なチューリングマシンによって非常にファイアーです。

NPでは、非決定的な方法で非決定的なものを使用しているため、計算ツリーのブランチは1つだけが受け入れられる必要があります（「同じ」時間に「すべて」の可能性を試します）。 Polynomicalyは非常にファイ可能な意味で、証明書（cとしましょう）があり、入力単語の解決策（wとしましょう）を持っていることを意味します。証明書は、入力長を考慮した多項式長でなければなりません。私たちのタスクは、証明書が解決策であるかどうかを確認することです。たとえば、SAT（満足度問題）では、証明書は正しい割り当てです（これは非決定論的に推測されます）。

したがって、あなたの問題はNPにあることを証明します：ペア（W、C）を検証するDTMが存在します。ここで、Wは入力数、Cはその要因です。 cの因子を掛け、それをwと比較する非常に困難なものを構築する必要があります。