どのようにp =できますか？ NPは整数因数分解を強化します

Question

$ { sf p} $が実際に$ { sf np} $に等しい場合、これにより整数をより速く因数分解するためにアルゴリズムをどのように強化しますか。言い換えれば、この事実はどのような洞察を与えてくれますか？

Answer 1

$ p = np $、そしてを解くことができるアルゴリズムがある場合 k-sat 多項式時間の問題では、整数の因数分解は、ファクタリングをK-SATの問題として説明することにより、単にK-SATに減らすことができます。

基本的には次のように機能します。$ p $、$ q $、および$ n $のビットを表すそれぞれの変数を作成します。次に、k-satの問題を$ p*q = n $として定式化します。 $ n $がわかっているため、それらの値を設定できます。その場合、満足のいく割り当ては、有効な$ p $と$ q $を説明します。 K-SATの乗算を説明するために、既知の乗算アルゴリズムを使用して、K-SATの論理回路を説明できます。 FactoringのK-Satへの還元に関する詳細については、参照してください ここ.

ファクタリングをよりよく理解するために、それはおそらくより多くの研究を必要とし、魔法のアルゴリズムを分析する必要があります（決定論的多項式時間でNP不完全な問題を解決することができます）。使用される乗算アルゴリズムに応じて、非常に特定の構造です）。

Answer 2

ファクタリングの決定問題は$ mathsf {np} $であり、ファクタリングは決定論的多項式時間でそれに減らすことができます。

$ mathsf {p} = mathsf {np} $の場合、Factoringを含む$ Mathsf {np} $の問題には、多項式時間アルゴリズムがあります。

現時点で考慮するための最もよく知られている決定論的/確率的アルゴリズムは指数関数的な時間をかけるため、多項式時間アルゴリズムが大幅に改善されることに注意してください。それを感じるために、2000ビット数を考慮することを検討してください。一方はビッグバン以来、すべての時間よりも時間がかかる場合があり、もう1つは数ミリ秒で答えることができます。