整数因数分解の問題をNP完全な問題に減らす

Question

私は、NPインターメディエットとNPコンプリートの関係を理解するのに苦労しています。 Ladnerの定理に基づいてp！= npの場合、NPまたはNP Completeでは言語のクラスが存在することを知っています。 NPのすべての問題はNP完全な問題に減らすことができますが、NPIの問題（整数因数分解など）をNP完全な問題に減らすための例は見られませんでした。このまたは別のnpi-> npc削減の例を知っている人はいますか？

Answer 1

たとえば、SATへのファクタリングの整然とした古典的な削減があります。これは、推定される「ハード」SATインスタンスの源でもあります。基本的に、SAT回路にエンコードされたバイナリ増殖にEEのアイデアを使用します。バイナリの乗算は、それぞれが乗数のビットによって「マスクされた」（anded）それぞれの一連の左シフトされた乗数の追加と考えてください。追加は、一連の完全な加算器であるバイナリ追加回路で実行できます。

才能のある学部生はこのアルゴリズムを構築できます。文献で最初に提案または実装された場所がわかりません。参考文献を聞きたいと思います。

例を参照してください これを満たす：Stefan SchoenmackersとAnna Cavenderによる満足度ソルバーを使用した素数化を解決する試み それを詳細に説明します。また Dimacsは挑戦しました 90年代後半から、一部の研究者によって生成されたファクタリングインスタンスがありましたが、おそらくアルゴリズムはその時代に論文で別々に書き込まれていませんでした。

Answer 2

絶対に明確にするために、整数の因数分解はNPインターメディーであるとは知られておらず、NPの完全性の証明または多項式時間アルゴリズムのいずれかの欠如に基づいていると疑われています（両方に多くの作業が置かれています）。 PとNPが異なる場合、間違いなくNPインターメディーである自然な問題（つまり、ラドナーによって作成されたものではありません）はわかりません。

さて、その免責事項の後、 グラフ同型 自然なNPインターメディエート問題のもう1つの候補です。それから単純な多項式時間の減少があります サブグラフ同型 - グラフを同じままにしてください！グラフ同型は、両方のグラフが同じサイズのサブグラフ同型の特別なケースです。最後のタッチは、そのサブグラフ同型です は NPコンプリート。

それとは別に、もちろん、それほど説明のない削減は常にあります クックレビン定理, 、NPインターメディーの問題には、それを決定する非決定的多項式時間チューリングマシンがあることを知っており、これをSATのインスタンスに変換できます（TMを構築する必要があります！）。