スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

P≠NP予想とは

P≠NP予想の大まかな説明。

非決定性多項式時間プログラムとは

プログラムの入力sは、0と1を有限個並べた記号列である。その文字数をsの長さといい、|s|で表す。また、プログラムのステップ数を、その実行時間という。

プログラムが多項式時間内に停止するとは、ある自然数係数の1変数多項式f(X)が存在して、任意の入力sに対して、プログラムがf(|s|)以内の実行時間で停止することをいう。

非決定的な選択があってもよいプログラムを非決定性プログラムという。ここで、非決定的とは、どのように選択されるかは事前に決まっていないという意味である。つまり、同じ入力に対して選択が常に同じとは限らず、実行過程が複数存在しうる。

非決定性プログラムのうち、非決定的な選択を全く含まないものを決定性プログラムという。決定性プログラムにおいては、同じ入力に対して実行過程は一定である。

どのような実行過程を経ても多項式時間内に停止するような非決定性プログラムを非決定性多項式時間プログラムという。そのうち、決定性プログラムであるものを決定性多項式時間プログラムという。

決定問題がプログラムで解けるとは

C(x)を命題関数とするとき、与えられたモノaが命題C(a)を満たすかどうかを判定する問題を決定問題という。命題を満たすかどうかの判定対象であるモノを対象物という。

決定問題が非決定性プログラムで解けるとは、各々の対象物aについて、それを0と1の記号列でコード化してプログラムに入力すると、

  • aが命題C(a)を満たすならば、可能な実行過程のなかで1が出力されるものが存在し、
  • aが命題C(a)を満たさないならば、どのような実行過程を経ても常に0が出力される

ときにいう。

決定性プログラムにおいては、同じ入力に対して実行過程は一定である。したがって、決定問題が決定性プログラムで解けるとき、各々の対象物aについて、それを0と1の記号列でコード化してプログラムに入力すると、それが命題C(a)を満たせば常に1が出力され、満たさなければ常に0が出力される。

P≠NP予想とは

NP問題とは、非決定性多項式時間プログラムで解けるような決定問題である。NP問題の全体からなる集合をNPで表す。

NP問題のうち、決定性多項式時間プログラムで解けるものをP問題という。P問題の全体からなる集合をPで表す。例えば、与えられた自然数が素数かどうかを判定する問題、いわゆる素数判定問題はP問題である。このことは、Agrawal、Kayal、Saxenaの3人によって証明された。

2つの集合PとNPは等しくならないという主張がP≠NP予想である。PはNPの部分集合なので、NPがPに含まれないこと、すなわち、NP問題のなかにP問題でないものが存在することが、予想の実質的な内容である。

NP完全問題とは

NP問題のなかには、その問題がPに属することが証明できると他のすべてのNP問題もPに属することが証明できるというものがある。そのようなNP問題のことをNP完全問題という。

NP完全問題の例は数多く知られている。以下はそのほんの一部である:

  • ハミルトン閉路問題:与えられたグラフについて、ある頂点から出発してすべての頂点をちょうど1回ずつ通って出発点に戻るような経路が存在するかどうかを判定する
  • 部分和問題:与えられた自然数の有限集合Sと自然数bについて、Sの部分集合でその元の総和がbに等しいものが存在するかどうかを判定する
  • 充足可能性問題:与えられた命題論理式について、命題変数への真偽値の割り当て方法で、もとの命題論理式が真になるようなものが存在するかどうかを判定する

参考文献

  • 鹿島亮『C言語による計算の理論』(サイエンス社)
  • 渡辺治『計算可能性・計算の複雑さ入門』(近代科学社)
  • 一松信ほか『数学七つの未解決問題』(森北出版)
  • Agrawal, M., Kayal, N., Saxena, N.: Primes is in P. Ann. Math. 160, 781-793, 2004

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。