最初に理解することは、PとNPが問題 これが何を意味するのかを理解するには、まず他の定義が必要です。
アルファベットは、空でない有限の記号の集合です。P>
{01}はascii文字セットと同様にアルファベットです。 {}は空であるため、アルファベットではありません。 N（整数）は有限ではないため、アルファベットではありません。p>
Σをアルファベットとします。 Σからの有限個の記号の順序付けられた連結はΣ上の単語と呼ばれます。文字列
10101penguinは、ASCII文字を含むアルファベット上の単語です。 数字πの10進表記は、アルファベット上の単語ではありません{.012301233156789}それは有限ではありません。p>単語wの長さは、|w|と書かれ、その中のシンボルの数です。たとえば、|
hello|=5および|ε|=0です。 任意の単語wに対して、|w|≤Nであり、したがって有限である。p>Σをアルファベットとします。 集合Σにはσを含むσ以上のすべての単語が含まれています。 集合Σ+には、εを除く、Σ以上のすべての単語が含まれています。 N≤Nの場合、Σ Nは長さnの単語の集合です。
すべてのアルファベットΣ、Σ、σ+は無限可算集合です。 ASCII文字セットΣ ASCIIの場合、正規表現
.*.+はそれぞれΣ ASCII＊とΣ ASCII+を表します。p>{
01}7は7ビットASCIIコードのセットです{0000000000000111111110000000111111101}32は32ビット整数値のセットです。Σをアルファベットとし、L⊆Σ ＊とします。 LはΜ上の言語と呼ばれています。
アルファベットΣの場合、空集合とΣ ＊はσ以上の自明な言語です。 前者はしばしば空の言語と呼ばれます。 空の言語{}と空の単語{ε}のみを含む言語は異なります。非NaN IEEE754浮動小数点値に対応する{
01}32のサブセットは有限言語です。言語は無限の数の単語を持つことができますが、すべての言語は数えることができます。言語は無限の数の単語を持つことができま The set of strings {
12, …} denoting the integers in decimal notation is an infinite language over the alphabet {012345678923571135111111?\d+\.\d*(?\d+)?に一致するすべての単語を含む言語は、ASCII文字セット（Cプログラミング言語で定義されている有効な浮動小数点式のサブセ実数の集合は可算ではないため、すべての実数を含む言語は（任意の表記法で）ありません。実数の集合は可算ではないため、すべての実数を含む言語は
Σをアルファベットとし、L⊆Σ ＊とします。 マシンDは、すべての入力w∈Σ ＊に対して、有限時間で特性関数xl(w)を計算する場合、Lを決定します。 特性関数は次のように定義されます
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.そのようなマシンはLのデシダと呼ばれます。”wが与えられた場合、D出力x”に対して”D(w)=x”と書きます。p>
多くのマシンモデルがあります。 今日実用的に使用されている最も一般的なものは、チューリングマシンのモデルです。 チューリングマシンは、セルにクラスタ化された無制限の線形記憶装置を持 各セルは、任意の時点でアルファベットの正確に一つのシンボルを保持することができます。 チューリングマシンは、一連の計算ステップとして計算を実行します。 各ステップでは、1つのセルを読み取り、その値を上書きし、読み取り/書き込みヘッドを1つの位置で左または右のセルに移動することができます。 マシンが実行するアクションは、有限状態オートマトンによって制御されます。
有限の命令セットと無制限の記憶域を持つランダムアクセスマシンは、チューリングマシンモデルと同じくらい強力な別のマシンモデルです。
この議論のために、私たちが使用する正確な機械モデルを気にするのではなく、機械が有限の決定論的制御ユニット、無制限の記憶装置を持ち、計算を数列のステップとして実行すると言えば十分です。あなたの質問でそれを使用したので、私はあなたがすでに”big-O”表記法に精通していると仮定しているので、ここでは簡単な復習に過ぎません。p>f:N→を関数とする。
f:N→を関数とする。 集合O(f)はすべての関数g:N→Nを含み、定数n0≤Nとc≤Nが存在し、n>n0を持つすべてのn≤Nに対してg(n)≤c f(n)が真である。p>
今、私たちは本当の質問にアプローチする準備ができています。
クラスPには、Lと定数k≤Nを決定するチューリングマシンDが存在するすべての言語Lが含まれており、すべての入力w数学的には正しいが、o（n≥nk）は読み書きに不便であるため、ほとんどの人は正直に言うと、私以外のすべての人は通常単にO（nk）を書きます。
境界はwの長さに依存することに注意してください。 単純にすべての可能な要因を試すよりも高度なアルゴリズムを使用すると、入力がバイナリ（または他のベース）でエンコードされている場合、素数の言 （大規模な関心にもかかわらず、これはManindra Agrawal、Neeraj Kayal、およびNitin Saxenaが2004年に受賞した論文でのみ証明できたため、アルゴリズムはそれほど単純ではないと推測で自明な言語{}とΤと自明でない言語{τ}は明らかにpにあります（任意のアルファベットτに対して）。 文字列を入力として受け取り、文字列がこれらのそれぞれの言語の単語であるかどうかを示すブール値を返し、関数が多項式の実行時の複雑さを持
すべての正規言語（正規表現で記述される言語）はPにあります。
Σをアルファベットとし、L⊆Σ ＊。 符号化された2つの単語w,c∞のタプルをとり、有限のステップ数の後に0または1を出力する機械Vは、次の性質を持つ場合、lの検証者です。(w,c)が与えられたとき、Vはw≤Lの場合にのみ1を出力します。
すべてのw≤Lに対して、v(W,c)=1となるようなc≤が存在します。 上記の定義のcは、証人（または証明書）と呼ばれています。
検証者は、wが実際にLにある場合でも、間違った証人に対して偽陰性を与えることが許可されています。 また、言語の各単語に対して、少なくとも一つの証人が存在することが必要です。
素数ではないすべての整数の十進エンコーディングを含む言語複合の場合、証人は因数分解になる可能性があります。 たとえば、
(659, 709)467231∈COMPOSITEの証人です。 あなたは簡単に467231が素数ではないことを証明し、与えられた証人なしながら、紙の上にコンピュータを使用せずに困難であることを確認することがで適切な証人がどのように見つけられるかについては何も言いませんでした。 これは非決定論的な部分です。クラスNPには、Lと定数k≤Nを検証するチューリングマシンVが存在するすべての言語Lが含まれており、すべての入力(w,c)に対して、Vは関数T≤O(n≤nk)の最大T(|w|)ステップの後に停止します。
上記の定義は、各w∈Lに対して、|c|≤T(|w|)を持つ証人cが存在することを意味することに注意してください。 （チューリングマシンは、証人のより多くのシンボルを見ることはできません。NPはPのスーパーセットです（なぜですか？）
NPはPのスーパーセットです（なぜですか？）
). NPにはあるがPにはない言語が存在するかどうかは分かっていません。
整数分解は言語自体ではありません。 しかし、それに関連する意思決定問題を表す言語を構築することができます。 つまり、nがd≤mの因子dを持つようなすべてのタプル(n,m)を含む言語です。 因子を決定するアルゴリズムがある場合は、各素因数に対して再帰的な二分探索を実行することにより、多項式のオーバーヘッドのみで完全な因数分解を計算するために使用することができます。その因子がNPにあることを示すのは簡単です。
適切な目撃者は単に因子d自体であり、検証者がしなければならないのは、d≤m and n mod d=0。 これはすべて多項式時間で行うことができます。 （数えられるのはエンコーディングの長さであり、それはnの対数であることを忘れないでください。）
因子もPにあることを示すことができれば、 （そして、あなたは今日の暗号のかなりの部分を壊しました。NPのすべての言語に対して、それを決定論的に決定するブルートフォースアルゴリズムがあります。 それは単にすべての証人の上に網羅的な検索を実行します。 （証人の最大長は多項式で囲まれていることに注意してください。）だから、素数を決定するためのあなたのアルゴリズムは、実際には合成を決定するためのブルートフォースアルゴリズムでした。あなたの最後の質問に対処するために、我々は削減を導入する必要があります。
あなたの最後の質問に対処するために、 削減は理論計算機科学の非常に強力な概念です。 ある問題を別の問題に減らすことは、基本的に別の問題を解決することによってある問題を解決することを意味します。P>
Σをアルファベットとし、AとBをΣ以上の言語とする。 Aがbに還元可能な多項式時間多-1であるとは、以下の性質を持つ関数f:Ƒ→Ƒが存在するときに言う。すべてのw∈に対してw∈A∩f(w)∈B。
関数fは、|w|の多項式で囲まれたステップ数のすべての入力wに対してチューリングマシンによって計算できます。たとえば、三角形を含むすべてのグラフ（隣接行列としてエンコードされた）を含む言語をAとします。 たとえば、三角形を含むすべてのグラフ（隣接行列としてエンコードされた）を含む言語をAとします。 （三角形は長さ3のサイクルです。)さらにBをゼロ以外のトレースを持つすべての行列を含む言語とする。 （行列のトレースは、その主な対角要素の合計です。 これを証明するためには、適切な変換関数fを見つける必要があります。fこの場合、隣接行列の3乗を計算するようにfを設定することができます。 これには2つの行列-行列積が必要で、それぞれが多項式の複雑さを持っています。（あなたはそれを正式に証明できますか？）
それはl∈p Lであることは自明である。
あなたはそれを正式に証明できますか？これをNPに適用します。
ある言語LがNP困難であるための必要十分条件は、すべての言語L’≥NPに対してL’≥Plであることである。
NP困難な言語は、NP自体にある場合とそうでない場合があります。
ある言語LがNP完全であることと
- L≠NPかつ
- LがNP困難であることは同値である。
- LがNP完全であることと
- LがNP困難であることとは同値である。
- lがNP完全であることは同値である。
最も有名なNP完全言語はSATです。 これには、満たすことができるすべてのブール式が含まれています。 たとえば、（A∩b）∩（A∩b）SAT SATです。 有効なミラーリング監視は{a=1,b=0}です。 式（A∧b）∧（A∧b）∧（a∧b）∧（A∧b）∧（A∧b）∧（A∧b） （あなたはそれをどのように証明しますか？SAT≠NPであることを示すことは難しくありません。 SATのNP硬度を示すことはいくつかの作業ですが、1971年にStephen Cookによって行われました。その1つのNP完全言語が知られていれば、還元を介して他の言語のNP完全性を示すことは比較的簡単でした。
NP完全言語が知られていれば、他の言語のNP完全性を示すことは比較的簡単でした。 言語AがNP困難であることが知られている場合、A⊆pbであることを示すと、BもNP困難であることが示されます（”√p”の推移性を介して）。 1972年、リチャード-カープは、SATの（推移的な）還元を介してNP完全であることを示すことができる21の言語のリストを発表した。 （これは私が実際にあなたが読むべきであることをお勧めするこの答えの唯一の論文です。 他のものとは異なり、理解するのは難しくなく、還元によるNP完全性の証明がどのように機能するかについて非常に良い考えを与えます。)
最後に、短い要約。 記号NPHとNPCを使用して、それぞれNP-hard言語とNP-complete言語のクラスを示します。
- p&サブセット;NP
- NPC&&&サブセットサブセットサブセットサブセットサブセット; NP-全&サブセット;NPH、実際にNPC=NP∩NPHにより定義
- (A∈NP)∧(B∈NPH)⇒A≦p B
注意のヌクレオ&サブセット;NPは適切な場合にもP=NP. これを見るには、自明でない言語を自明な言語に還元することはできず、Pには自明な言語とNPには自明でない言語があることを明確にしてくださ しかし、これは（非常に興味深いものではない）コーナーケースです。混乱の主な原因は、実際に入力の長さを参照しているときに、アルゴリズムの入力の解釈として「O（n≤f（n））」の「n」を考えていたことです。 これは、アルゴリズムの漸近的な複雑さが入力に使用されるエンコーディングに依存することを意味するため、重要な区別です。
今週、知られている最大のメルセンヌ素数の新しい記録が達成されました。 現在知られている最大の素数は次のとおりです274 207 281 − 1….. この数は非常に巨大なので、頭痛になるので、次の例では小さいものを使用します: 231 – 1 = 2 147 483 647. これは、さまざまな方法でエンコードすることができます。10進数として:
2147483647(10バイト)単項番号として: 11111…112147483647…は2 147 483 640以上に置き換えられます1s（ほぼ2gib）これらの文字列はすべて同じ番号をエンコードし、これらのいずれかを与 （必要に応じて、10進エンコーディングを2進数、8進数、または16進数に置き換えることができます。 長さは一定の係数だけ変更されます。)
素数性をテストするための素朴なアルゴリズムは、単項符号化のための多項式のみです。 AKSの素数検定は、10進数（または他の任意の底b≥2）の多項式です。 Lucas-Lehmer素数検定は、Pを奇数素数とするメルセンヌ素数Mpの最もよく知られたアルゴリズムであるが、メルセンヌ指数p（pの多項式）のバイナリ符号化の長さは依然として指数関数的である。
アルゴリズムの複雑さについて話したいのであれば、どの表現を使用するかを非常に明確にすることが非常に重要です。 一般に、最も効率的な符号化が使用されると仮定することができる。 つまり、整数のバイナリです。 （すべての素数がメルセンヌ素数であるわけではないので、メルセンヌ指数を使用することは一般的な符号化方式ではないことに注意してください。理論的な暗号化では、多くのアルゴリズムには、最初のパラメータとしてk
1の完全に役に立たない文字列が正式に渡されます。 アルゴリズムはこのパラメータを見ることはありませんが、手続きのセキュリティを調整するために使用されるセキュリティパラメータであるkの多項式に形式的にすることができます。バイナリ符号化の決定言語がNP完全であるいくつかの問題では、埋め込み数の符号化が単項に切り替わると、決定言語はNP完全ではなくなります。 他の問題の決定言語は、その場合でもNP完全のままです。 後者は強くNP完全と呼ばれます。 最もよく知られている例は、ビンの梱包です。
入力が圧縮されている場合、アルゴリズムの複雑さがどのように変化するかを見ることも（そしておそらくもっと）興味深いことです。 メルセンヌ素数の例では、3つのエンコーディングが見られ、それぞれが以前のものよりも対数的に圧縮されています。
1983年、Hana GalperinとAvi Wigdersonは、グラフの入力エンコードが対数的に圧縮されたときの一般的なグラフアルゴリズムの複雑さについて興味深い論文を書いています。 これらの入力に対して、上から三角形を含むグラフの言語（明らかにPにあった）は突然NP完全になります。pやNPのような言語クラスは、問題ではなく言語用に定義されているためです。
そして、それはPやNPのような言語クラスが言語用に定義されてい