NP - Wikipedia
計算複雑性理論における NP (英: Non-deterministic Polynomial time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。 NP は、NTIMEを使って次のように定義される[1]。 つまり、非決定性チューリングマシンによって多項式時間で解ける決定問題のクラスであり、名称も 英: Non-deterministic Polynomial time（非決定性多項式時間）の略である。また、多項式時間検証可能という同値な定義もある。言語 が NP に属するとは、多項式時間決定性チューリングマシン と多項式 が存在し、次の性質を満たすことを言う。 ならば、ある証拠 が存在し、 ならば、どんな証拠 でも、 ハミルトン閉路問題は、「与えられたグラフについて、全ての頂点を一度だけ通る閉路(ハミ
多項式時間変換 - Wikipedia
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。 ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」といい、 と書く。 ただしここでの変換は A の入力内容に依存してはならない。つまり A という問題の全パターンが B に変換できなければいけない。 この概念は計算理論において問題の「難しさ」の度合いを測
多項式時間 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "多項式時間" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年9月) 多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズに対して、処理時間の上界としての多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数に対して要素の比較・交換を行う回数は高々 である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてと表される
)
P (計算複雑性理論) - Wikipedia
Pはしばしば、「効率的に解ける」問題のクラスとして扱われる。しかしながら、RPやBPPといった乱択で解けるクラスも、Pより大きいかもしれないが「効率的に解ける」と考えることもできる。逆にPに属しても実際には扱うことが困難である問題もある。例えば、入力のサイズnに対してn1000000の時間を必要とする問題も、定義からはPに属する。 Pに属する問題のうち対数領域還元に関して最大なものはP完全であるという。 非決定性チューリング機械によって多項式時間で解かれる判定問題のクラスをNPという。PがNPに含まれることは自明である。多くの研究者がPはNPの真部分集合であると信じているが、証明されていない（P≠NP予想）。 対数領域の決定性チューリング機械で判定可能な問題のクラスであるLはPに含まれるが、L = Pかどうかは未解決である。対数領域の交替性チューリング機械によって解ける問題のクラスALOG
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
