NP問題における決定問題とはなにか

アルゴリズムの話をする際に良く出てくるPやNP、NP完全というものを一度きちんと勉強しておきたいと思いブログを書いていましたが、長くなりすぎたため4部作にしました(本記事はpart1)。本記事では下準備としてNP問題であるための条件「決定問題」というものの解説をします。学習には以下の本を使っています。

組合せ最適化第2版 (理論とアルゴリズム)

作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
出版社/メーカー: 丸善出版
発売日: 2012/02/29
メディア: 単行本
クリック: 5回
この商品を含むブログ (1件) を見る

まずは決定問題が扱う「言語」という概念から説明します。

言語

計算量理論は大部分が決定問題に基づいている。実際、任意の言語L⊆{0,1}*は、決定問題,すなわち,与えられた0-1文字列がLに属するか(どうかを)決定する問題,と解釈できるからである。(p419)

言語とあるが、これは一般的な自然言語でもプログラミング言語の意味でもない。何らかのデータを符号化したものと考えられる。言語{0,1}*は何らかの011001011...と続く01の羅列、即ちバイナリであることを前提としている。決定問題は上記の文通り、あるバイナリが言語Lに属するかどうかを決定する問題のこと。

決定問題の定義

決定問題(decision problem)は多項式時間で決定できる言語Xとその部分集合Y⊆Xの対P=(X,Y)として定義される。

注意)このP=(X,Y)のPは複雑性クラスのP,NPのPではありません。本中では斜体にして区別している。

ここで{0,1}* ⊇ X ⊇ Yという言語間の包含関係が成り立つ集合X,Yを定義。なお任意のバイナリが{0,1}* ⊇ Xであるかはどうかは多項式時間で決定できる必要がある*1。この事を組合せ最適化の本ではハミルトン閉路問題を例に説明している

全ての2新文字列がハミルトン閉路問題のインスタンスというわけではなく、無効グラフを表すものだけがそのインスタンスである。本書で扱うほとんどの興味深い決定問題において、インスタンスは0-1文字列集合の真部分集合である。任意の文字列が正しいインスタンスであるかどうかを多項式時間で決定できることが必要である。(p420)

インスタンス

言語Xの任意の元をインスタンスと呼ぶ。

Xの要素をPのインスタンスという

インスタンスは以下の２つのものに分類できる

Yの要素がyes-インスタンス

X/Yの要素がNo-インスタンス(p420)

補足:X/Yは集合XからYを引いた差集合のこと。

決定問題(X,Y)に対するアルゴリズム

x∈Yならばf(x)=1, x∈ X/Y ならばf(x)=0となる関数f:X→{0,1}を計算する(p420)

Xの任意の元がYに属しているかを判定するアルゴリズムのこと。

yes-インスタンスを与えれば1
No-インスタンスを与えれば0

を変えてして問題の任意のインスタンスを判定できる必要がある。

証明検証アルゴリズム

P=(X,Y)に対してP'=(X',Y')という多項式時間で処理できる決定問題(証明検証アルゴリズム)を定義する。X'とY'は以下のように示される

X':={x#c: x∈X, c∈{0,1}^[p(size(x))]}

Y = {y∈X:y#c∈Y'であるようなc∈{0,1}^[p(size(y))]が存在する}

シンボル#,文字列cをこの順に連結した文字列を表す。(p421)

[p(size(x))]というシンタックスはxのサイズにしたがって多項式サイズで増えるという意味。[value]は床関数のシンタックスです

ja.wikipedia.org

決定アルゴリズムに対して、証明検証アルゴリズムは扱える問題のインスタンスはyes-インスタンスの処理のみで十分でありNo-インスタンスの検証を要求されないが、処理速度は多項式時間を要求される。決定アルゴリズムの時点で速度が十分ある(任意の問題を多項式時間で決定できる)場合は決定アルゴリズムをそのまま証明検証アルゴリズムに流用することができる。決定アルゴリズムを使った検証では#cが不要になる。