microbeの活動日記

プログラミングコンテストとか勉強とかいろいろ

胎児から始める計算複雑性理論 P≠NP予想編

はじめに

絢辻詞に踏まれたい

わかりやすくするために厳密なところは欠いています.突っ込まないで

 

P≠NP予想とは

P≠NP予想の説明をWikipediaから抜粋すると

P≠NP予想(P≠NPよそう、P is not NP)は、計算複雑性理論(計算量理論)におけるクラスPクラスNPが等しくないという予想である。P対NP問題(PたいNPもんだい、P versus NP)と呼ばれることもある。

わかる人にはそのままだと思いますが,わからない人には全然わからないと思います.ぼくにはわかりません.

そもそもこの説明を理解するにはPやNPなどの用語を理解する必要があるので,最初はこれらの用語から説明していこうとおもいます.

用語の説明

判定問題

判定問題は決定問題とも呼ばれ,入力に対して[1 / 0] や [Yes / No]などのいずれかしか出力しない問題を指します.例を挙げると,整数Nが素数か否かを判定する問題も判定問題となります.

 

決定性チューリングマシン

そもそもチューリングマシンとはなんぞやという話なんですが,
チューリングマシン(機械)は計算模型のひとつで,計算機を数学的に議論するために単純化・理想化された仮想機械のことです.

チューリングマシンは無限の長さを持つテープと有限状態機械(有限オートマトン)から構成され,原理としてはこのようになっています.

チューリングマシンはあらかじめ設定された幾つかの「状態」を持っており、その「状態」とヘッドから読み出したデータの組み合わせによって、「ヘッドをテープ上で一マス移動させる」「テープのヘッドのあるマスにデータを書き込む」「『状態』を変更する」のいずれかの動作を行う。その後、移動後のヘッド位置からデータを読み込み、そのデータと新しい「状態」の組み合わせに従って、次の動作を行う。

 難しそうに見えますが乱暴な言い方をすると,「手順に従ってテープへの読み書きやテープ上の移動とかをやっていくよー」ということになります.この手順がいわゆる”アルゴリズム”と言われるものになります.

特に決定性チューリングマシンとは,入力xに対して出力yが一意に定まっているものを言います.

チューリングマシンは仮想機械のことですが,現代の一般的なコンピュータは決定性か非決定性かは置いといて,このチューリングマシンに基づいて設計されています.言うなればテープがメモリ,有限状態機械がCPUに相当します.

 

非決定性チューリングマシン

チューリングマシンと決定性チューリングマシンについては前述しましたが,非決定チューリングマシンでは入力xに対して出力 yは一意に定まっておらず,状態遷移がその都度,問題を効率的に解けるように選択されていくマシンのことを言います.

 

多項式時間還元

Wikipedeaから概要を抜粋すると

ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」といい、  と書く。 ただしここでの変換は A の入力内容に依存してはならない。つまり A という問題の全パターンが B に変換できなければいけない。

となっています.わかるか?おれにはわからない.

例えば問題Aの問題例と問題Bの問題例の2つにおいて,問題Aの各問題はすべて問題Bとして捉えなおすことができるとします.その捉えなおす作業を決定性チューリングマシンを用いて多項式時間で捉えなおすことができるとき,問題Aは問題Bに多項式時間変換可能であるといいます.
また,概要にある通り,問題Aの全パターンが問題Bとして捉えなおさなければなりません.

 

P

クラスPは定義によると「判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体をPで表す。」となっています.

クラスPを大雑把に説明すると,判定問題のうち多項式(積和で表される式)時間で解ける問題の集合のことを指します.O記法を用いたものだと,O(n^2)は多項式オーダーなので多項式時間で解くことができますが,O(2^n)は指数部に変数を持っており指数オーダーとなってしまい,これはNPというクラスに属します.

問題例としては,ダイクストラ法やオイラーグラフ(グラフを一筆書きできるかどうか)が挙げられます.

 

NP

クラスNPは複雑性クラスのひとつで,Non-deterministic Polynomial time(非決定多項式時間)の略で定義は次の2つになります.

  1. 非決定性チューリングマシンによって多項式時間で解くことができる問題。
  2. yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式で判定できる問題。

誤解されがちなんですが,NPは多項式時間で解けない問題つまりNot Pのことではありません.

クラスNPを端的に説明すると「答えを見つけるには計算量がどうなるのか分らないけど答えが正しいかどうかを確かめるのは多項式時間で出来るよ」ってことになります.
また,クラスNPも判定問題,つまりはYes/Noで答えられるものでないとそれはNPではありません.

クラスPも多項式時間で解くことができる以上,答えの正しさの証明も多項式時間で出来るためクラスPはクラスNPに含まれます.

問題例はNP完全の説明と一緒に挙げます.

 

NP困難 

NP困難(NP-hard)とは,問題が「NPに属する任意の問題と比べて,少なくとも同等以上に難しい」ことです.定義は「NPに属する任意の問題LがHへ帰着可能である」とされています.何言ってるのかわからないですね.

簡単にまとめると「”少なくとも”NPと同等以上に難しい問題」ということになります.また,NP困難は必ずしもクラスNPに属するかはわかりません.

NP困難な問題の例としては,巡回セールスマン問題やナップザック問題が挙げられます.

 

NP完全

NP完全問題(NP-complete problem)とは,

  1. クラスNPに属する決定問題
  2. 任意のクラスNPに属する問題から多項式時間還元可能なもの

のことをいいます.

簡単に説明するとNPかつNP困難であり,多項式時間還元可能なもののことです.
NP完全はNPの中では最も難しい問題になります.

NP(完全)の問題例としては,3-SATや部分和問題,ハミルトン閉路などが挙げられます.

 

改めてP≠NP予想とは

これらの用語を説明すればあとは初見よりはわかるとは思います.

P≠NP予想とは,NPはPを含みますが,PとNPは等しくないという予想になります.

多くの研究者はP≠NPと信じています.ですが,P=NPと予想する研究者もいないわけではありません.詳しくはググってください.

仮にP=NPが示された場合,指数オーダーアルゴリズムしか見つかっていない様々な問題に対して効率的な多項式アルゴリズムが存在する可能性を示すことになります.

また,予想とあるように,P≠NPはまだ証明されていません.P≠NP予想はミレニアム懸賞問題として懸賞金100万ドル(およそ1億円)がかけられています.

 

まとめ

1億円ほしい.