、たとえばO(1), O(n1/2), O(n2), O(n3)など。問題がPに属する場合、多項式時間で最初から問題を解決できるアルゴリズムが少なくとも1つ存在します。たとえば、2 <= k <= sqrt(n)をループし、各ステップでiv id = “かどうかを確認することで、整数nが素数であるかどうかを常に判断できます。 dfcc1ec3cb “> はnを除算します。

NPは非決定論的な多項式の複雑さです。非決定論的であるとはどういう意味かよくわかりません。多項式時間で検証するのは簡単だと思いますが、まだ知らなかった場合は、最初から解く多項式時間である場合とそうでない場合があります。回答。 多項式時間で解ける可能性があるため、すべてのP問題はNP問題でもあります。 NPの例として素因数分解が引用されていますが、試行因数分解にはO(sqrt(n))時間がかかるため、個人的にはPではない理由がわかりません。

NP完全問題はまったくわかりませんが、その一例として巡回セールスマン問題が挙げられています。しかし、私の意見では、TSP問題はNPだけかもしれません。なぜなら、前もってパスが与えられているかどうかを確認するには、O(2n n2) time to solve, but O(n)のようなものが必要だからです。

NP困難はちょうどいっぱいだと思います不明な点があります。検証が難しく、解決が困難です。

コメント

• CSに関する質問を読んだことがありますか。 SE P、NP、NP完全、およびNP困難の定義は何ですか？？
• 私は’まだそのリンクを見ていません、いいえ。’読み直します、ありがとう
• CS.SEの答えは非常に畏敬の念を起こさせます、しかし、’は、これらの用語が何を意味するのかを、あまり詳細に説明することなく、非常に簡潔で誤解を招かないように説明することが可能だと思います。 、”要点答えますか、それともCS.SEの投稿で問題は解決しますか？
• @MichaelTそのリンクを読んだところ、非常に冗長で、いくつかの点であまり明確ではありませんでした。答えよりも質問が多かったような気がします。
• “非決定性”は次のように解釈できます。 “選択肢が与えられると、コンピューターは毎回正しい選択肢を選択します”。

回答

。

@Nakano：big-O表記では、nは入力のサイズ（要素数、バイト数、桁数など）の尺度であり、の値ではありません。入力。

@Nakano簡単に言うと、’は大丈夫です。これが、タイムコを行うときに理由です。複雑さの分析常にnの意味を指定する必要があります。 nが”入力のサイズ”であるという主張は、通常nを定義する方法の簡潔な要約にすぎません。 ‘は、big-O表記や時間計算量の厳密な定義の一部ではありません。 nが入力の値である場合、整数因数分解はO（sqrt（n））であると言うのは正しいと思います。たまたま、nがサイズを意味する複雑さの結果は、nが値を意味する結果よりも実際にははるかに便利です。

@Nakano It ‘また、技術的に、プリミティブ演算（加算、乗算、メモリからの読み取り、メモリへの書き込み、2つの数値の比較）の時間計算量も定義する必要があることも覚えておく価値があります。ほとんどの場合、これらのプリミティブはすべて一定であると想定するか、1種類の操作のみをカウントします（たとえば、ソートアルゴリズムの場合、従来は比較をカウントしていました）。素因数分解の結果は、’これらの操作がすべて通常のように一定時間であるとは想定していません。そうでない場合、数値のサイズは’非常に重要です。

回答

回答

、 ε を含む。セット Σ ⁺ には、 Σ のすべての単語が含まれています。 i>、 ε を除く。 n ∈ N の場合、 Σ ⁿ は、長さ n の単語のセットです。

Forすべてのアルファベット Σ 、 Σ ^＊ と Σ ⁺ は無限です可算集合。ASCII文字セット Σ _ASCII の場合、正規表現.*および.+は Σ _ASCII ^＊ と Σ _ASCII ⁺ それぞれ。

{0、1} ⁷ は、7ビットASCIIコードのセット{0000000、0000001、…、1111111}。 {0、1} ³² は、32ビット整数値のセットです。

Σ をアルファベットとし、 L ⊆ Σ ^＊ 。 L は、 Σよりも言語と呼ばれます。 div> 。

アルファベットの場合 Σ 、空集合と Σ ^＊ は

。前者はしばしば空の言語と呼ばれます。空の言語{}と空の単語のみを含む言語{ ε }は異なります。

{

、1} ³² は有限言語です。

言語には無限の数の単語を含めることができますが、すべての言語はカウント可能です。 10進表記の整数を示す文字列のセット{1、2、…}は、アルファベット上の無限言語です{0、1、2、3、4、5、6、7 、8、9}。文字列の無限のセット{2、3、5、7、11、13、…} 10進表記の素数は、その適切なサブセットです。正規表現[+-]?\d+\.\d*([eE][+-]?\d+)?に一致するすべての単語を含む言語は、ASCII文字セットを超える言語です（Cプログラミング言語で定義されている有効な浮動小数点式のサブセットを示します）。

実数のセットはカウントできないため、（表記法で）すべての実数を含む言語はありません。

Let Σ はアルファベットで、 L ⊆ Σ ^＊ 。マシン D はすべての入力に対して L を決定しますw ∈ Σ ^＊ 特性関数 χ _L （ w ）を有限時間で。特性関数は次のように定義されます

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

このようなマシンは決定者 for L 。 「与えられた w 、 D i」に対して「 D （ w ）= x 」と書く>出力 x ”。

多くのマシンモデルがあります。今日実用化されている最も一般的なものは、 チューリングマシン のモデルです。チューリングマシンには、セルにクラスター化された無制限の線形ストレージがあります。各セルは、任意の時点でアルファベットの記号を1つだけ保持できます。チューリングマシンは、一連の計算ステップとして計算を実行します。各ステップで、1つのセルを読み取り、その値を上書きして、読み取り/書き込みヘッドを1つの位置だけ左または右のセルに移動できます。マシンが実行するアクションは、有限状態オートマトンによって制御されます。

有限の命令セットと無制限のストレージを備えたランダムアクセスマシンは、チューリングマシンモデルと同じくらい強力な別のマシンモデルです。

この説明のために、使用する正確なマシンモデルに煩わされることはありませんが、マシンには有限の決定論的制御ユニット、無制限のストレージがあり、一連のステップとして計算を実行すると言えば十分です。

あなたは質問でそれを使用したので、あなたはすでに「big-O」表記に精通していると思いますここでは簡単に復習します。

f ： N →は関数です。セット O （ f ）には、すべての関数 g が含まれています： N →定数 n ₀ ∈ N bが存在するdiv> N >および c ∈ N で、すべての n ∈ N with n > n ₀ it g （ n ）≤ c f （ n ）。

これで、実際の質問に取り組む準備が整いました。

クラス P には、 Lを決定するチューリングマシン D が存在するすべての言語 L が含まれています。 および定数 k ∈ N で、すべての入力に対して w 、 D は、関数 T iv id = “ea6d47993e”の最大 T （| w |）ステップの後に停止します。 > O （ n ↦ n ^k ）。

O （ n ↦ n 以降> ^k ）は数学的には正しいですが、読み書きには不便です。正直なところ、私以外のほとんどの人は通常、単純に書くだけです。 O （ n ^k ）。

境界はの長さに依存することに注意してください。 w 。したがって、素数の言語に対して行う引数は、 unarayエンコーディングの数値に対してのみ正しいです。ここで、のエンコーディングは w 数値 n 、エンコーディングの長さ| w | n に比例します。実際には、このようなエンコーディングを使用する人は誰もいません。ただし、考えられるすべての要素を単純に試すよりも高度なアルゴリズムを使用すると、入力が2進数（または他のベース）でエンコードされている場合、素数の言語は P のままであることが示されます。 （大きな関心にもかかわらず、これは2004年の受賞歴のある論文で Manindra Agrawal、Neeraj Kayal、Nitin Saxena によってのみ証明されたため、アルゴリズムはそれほど単純ではありません。）

自明な言語{}および Σ ^＊ と自明でない言語{ ε }は明らかに P です（任意のアルファベット） Σ ）。文字列を入力として受け取り、文字列がこれらのそれぞれの言語からの単語であるかどうかを示すブール値を返す関数をお気に入りのプログラミング言語で記述し、関数の実行時の計算量が多項式であることを証明できますか？

すべての通常の言語（通常の式で記述される言語）は P です。

Σ をアルファベットとし、 L ⊆ Σ ^＊ 。 2ワード w 、 c ∈ のエンコードされたタプルを受け取るマシン V Σ ^＊ であり、有限のステップ数が

verifier for L （次のプロパティがある場合）。

• 指定（ w 、 c ）、 V は、 w ∈ L 。
• すべての w ∈ L について、 c ∈ Σ V （ w 、 c ）= 1となるようにします。

上記の定義の c は、証人（または証明書）と呼ばれます。 。

w が実際に L にある場合でも、検証者は間違った証人に対して偽陰性を与えることができます。ただし、誤検知を与えることは許可されていません。また、言語の単語ごとに、少なくとも1人の証人が存在する必要があります。

言語COMPOSITEの場合、プライムではないすべての整数の10進エンコーディングが含まれます 、証人は因数分解である可能性があります。たとえば、(659, 709)は467231 ∈ COMPOSITEの証人です。証人がいなくても、紙の上で467231が素数ではないことを証明することは、コンピューターを使用しないと難しいことを簡単に確認できます。

適切な証人がどのようにできるかについては何も言いませんでした。これは非決定論的な部分です。

クラス NP には、チューリングマシンが存在するすべての言語 L が含まれています L と定数 k ∈ N を検証するV 入力（ w 、 c ）、 V は、最大で T （| w ）後に停止します。 > |）関数の手順 T ∈ O （ n ↦ n ^k ）。

上記の定義は、 w ∈ L ごとに c の証人が存在することを意味していることに注意してください。 | c | ≤ T （| w |）。 （チューリングマシンは、証人のシンボルをこれ以上見ることができない可能性があります。）

NP は P のスーパーセットです（なぜですか？）。 NP にはあるが P にはない言語が存在するかどうかは不明です。

素因数分解はそれ自体が言語ではありません。ただし、それに関連する決定問題を表す言語を構築することはできます。つまり、 n の係数が d であるような、すべてのタプル（ n 、 m ）を含む言語です。 d ≤ m 。この言語をFACTORと呼びましょう。 FACTORを決定するアルゴリズムがある場合は、素因数ごとに再帰的な二分探索を実行することで、多項式のオーバーヘッドのみで完全な因数分解を計算できます。

FACTORが NP 。適切な証人は、単に要因 d 自体であり、検証者が行う必要があるのは、 d ≤ m および n mod d = 0。これはすべて、多項式時間で実行できます。 （繰り返しになりますが、カウントされるのはエンコーディングの長さであり、 n の対数であることに注意してください。）

FACTORが P にもあることを示すことができれば、多くのすばらしい賞を確実に獲得できます。 （そして、あなたは今日の暗号化のかなりの部分を破りました。）

NP のすべての言語には、決定するブルートフォースアルゴリズムがあります。 >決定論的です。すべての証人に対して徹底的な検索を実行するだけです（証人の最大長は多項式によって制限されることに注意してください）。したがって、PRIMESを決定するアルゴリズムは、実際にはCOMPOSITEを決定する力ずくのアルゴリズムでした。

最後の質問に対処するために、削減を導入する必要があります。削減は理論的コンピュータサイエンスの非常に強力な概念です。ある問題を別の問題に削減することは、基本的に、ある問題を別の問題を解決することによって解決することを意味します。問題。

Σ をアルファベットとし、 A と B は Σ の言語です。 A は関数 f が存在する場合、から B への多項式時間多対1還元可能： Σ ^＊ → Σ ^＊ 次のプロパティを使用します。

• w ∈ A   ⇔   f （ w ）∈ B  すべての w ∈ Σ ^＊ 。
• 関数 f は、すべての入力に対してチューリングマシンで計算できます w は、| w |の多項式で囲まれたいくつかのステップで実行されます。

この場合、 A iと記述します。 > ≤ _p B 。

の場合たとえば、 A を、三角形を含むすべてのグラフ（隣接行列としてエンコード）を含む言語とします。 （三角形は長さ3のサイクルです。）さらに B を、ゼロ以外のトレースを持つすべての行列を含む言語とします。 （行列のトレースは、その主対角要素の合計です。）この場合、 A は、 B に還元可能な多項式時間多対一です。これを証明するには、適切な変換関数 f を見つける必要があります。この場合、 f を設定して、隣接行列の3 ^rd 乗を計算できます。これには2つの行列-行列積が必要であり、それぞれに多項式の複雑さがあります。

L ≤ _{であることは自明です。 p} L 。 （正式に証明できますか？）

これを NP に適用します。

言語 L は NP -hard である場合に限り L “≤ _p L すべての言語 L ” ∈ NP 。

NP -ハード言語 NP 自体に含まれる場合と含まれない場合があります。

言語 L は NP -complete

• L ∈ NP および
• L は NP -ハードです。

最も有名な NP -完全な言語はSATです。満たすことができるすべてのブール式が含まれています。例：（ a ∨ b ）∧（¬ a ∨ ¬ b ）∈土。有効な証人は{ a = 1、 b = 0}です。式（ a ∨ b ）∧（¬ a ∨ b ）∧ ¬ b ∉ SAT。 （それをどのように証明しますか？）

SAT ∈ NP であることを示すのは難しくありません。 NP -SATの硬さを示すのはいくつかの作業ですが、1971年に Stephen Cook によって行われました。

1つの NP -完全な言語がわかったら、他の言語の NP -完全性を縮小によって示すのは比較的簡単でした。言語 A が NP -hardであることがわかっている場合は、 A ≤ _p B は、 B が NP ハードでもあることを示しています（「 _p ”）。 1972年、 Richard Karp は、SATの（推移的）削減によって NP であると彼が示すことができる21の言語のリストを公開しました。 （これは、私が実際に読むことをお勧めするこの回答の唯一の論文です。他の論文とは異なり、理解するのは難しくなく、削減による NP の完全性の証明がどのように機能するかについて非常に良い考えを与えます。 ）

最後に、簡単な要約です。記号 NPH と NPC を使用して、 NP -ハード言語と NP -完全言語のクラスを示します。それぞれ。

• P ⊆ NP
• NPC ⊂ NP および NPC ⊂ NPH 、実際には NPC = NP ∩ NPH の定義
• （ A ∈ NP ）∧（ B ∈ NPH ）  ⇒   A ≤ _p B

NPC ⊂ NP を含めることは、 Pの場合でも適切であることに注意してください。 = NP 。これを確認するには、自明でない言語を自明な言語に還元することはできず、 P にも自明な言語があることを明確にしてください。 NP の自明でない言語として。Thiただし、sは（あまり面白くない）コーナーケースです。

補遺

混乱の主な原因は、「 n 「 O （ n ↦ f （ n ））」は、実際に入力の長さを参照する場合の、アルゴリズムの入力の解釈として。これは、アルゴリズムの漸近的な複雑さが入力に使用されるエンコーディングに依存することを意味するため、重要な違いです。

今週、既知の最大の

メルセンヌプライムが達成されました。現在知られている最大の素数は2 ^{74   207   281} −1です。この数は非常に大きいです。頭痛の種になるので、次の例では小さい方を使用します：2 ³¹ – 1 = 2   147   483   647。さまざまな方法でエンコードできます。

• 10進数としてのメルセンヌ指数：31（2バイト）
• 10進数として：2147483647（10バイト）
• 単数として番号：11111…11ここで…は2   147 483   640以上の1（ほぼ2 GiB）

これらの文字列はすべて同じ数をエンコードし、これらのいずれかが与えられると、同じ数の他のエンコードを簡単に作成できます（10進数のエンコードを2進数、8進数、または16進数に置き換えることができます）あなたがしたい場合はmal。一定の係数で長さを変更するだけです。）

素数性をテストするための単純なアルゴリズムは、単項エンコーディングの多項式のみです。 AKS素数性テストは、10進数（またはその他の基数 b ≥ 2）の多項式です。 ）。 Lucas-Lehmer素数検定は、メルセンヌ素数 M _{p p は奇数の素数ですが、メルセンヌ指数 p （ p の多項式）のバイナリエンコーディングの長さでは依然として指数です。 。}

アルゴリズムの複雑さについて話したい場合は、使用する表現を明確にすることが非常に重要です。一般に、最も効率的なエンコーディングが使用されていると想定できます。つまり、整数の場合はバイナリです。 （すべての素数がメルセンヌ素数であるとは限らないため、メルセンヌ指数の使用は一般的なエンコードスキームではないことに注意してください。）

理論的な暗号化では、多くのアルゴリズムが完全に役に立たない k 1を最初のパラメーターとして使用します。アルゴリズムはこのパラメータを確認することはありませんが、 k で正式に多項式にすることができます。これは セキュリティパラメータ プロシージャのセキュリティを調整するために使用されます。

バイナリエンコーディングの決定言語が NP -completeである一部の問題では、決定言語は NP -埋め込まれた数値のエンコードが単項に切り替えられた場合に完了します。他の問題の決定言語は NP のままです-それでも完全です。後者は強く NP -完全と呼ばれます。最もよく知られている例は、 ビンパッキング です。

方法を確認することも（そしておそらくもっと）興味深いことです。入力が圧縮されると、アルゴリズムの複雑さが変化します。メルセンヌ素数の例では、3つのエンコーディングがあり、それぞれが前のエンコーディングよりも対数的に圧縮されています。

1983年、 Hana Galperin and Avi Wigderson は、グラフの入力エンコーディングが対数的に圧縮されている場合の一般的なグラフアルゴリズムの複雑さについて興味深い論文を書いています。これらの入力の場合、上からの三角形を含むグラフの言語（明らかに P にあった）は突然 NP -completeになります。

そしてそれ「 P や NP などの言語クラスは問題ではなく言語に対して定義されているためです。

コメント

• この回答は、質問者の理解レベルにはおそらく役に立たないでしょう。他の回答を読んで、ななこが苦労していることを確認してください。これはどう思いますか？答えは彼/彼女を助けますか？
• この答えはOPを助けないかもしれませんが、確かに他の読者（私を含む）を助けます。
• 非常に役立つ答え！数学記号を適切に修正しないことを検討する必要があります表示されます。

回答