Yabu.log

ITなどの雑記

PとNPについて

4部作その2。組み合わせ最適化第二版のp419~421の理解メモです。前回の決定問題の知識を前提に記事を書いています。 

yuyubu.hatenablog.com

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

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

Nondeterministicについてちょっと小話

ちょっとわかりにくいのがNPですね。Not Pではありません。この話題に入る前にNondeterministic Turing Machineドラえもんの秘密道具並みにヤバイ存在だということを頭に入れておくと、理解が深まります。NP問題を多項式時間で解くとされる「非決定性チューリング機械」は思考実験的アナロジーであり、任意のNP問題の非決定性アルゴリズム多項式時間で解く計算機は実存していません。

またNondeterministicという単語が一般的なシステム用語と少しスコープが違う使われ方をしているように感じます。*1

  • イメージとしてはこんな感じです。
    • △常に同じ答えを出さない
    • ⭕️常に最良の乱数を選ぶことができる

NPとP

  • NP:決定問題のうち、証明検証アルゴリズムがPで終わる証明(certificate)が存在しているもの。*2

クラスNPでは、多項式時間アルゴリズムは要求されず、任意のyes-インスタンスに対してのみ多項式時間で検証できる証明の存在だけが要求される。(p421)

多項式時間アルゴリズムが存在する全ての決定問題のクラスをPで表す。(p420)

証明検証アルゴリズムの箇所にも書いたが、Pの決定アルゴリズムはそのまま判定アルゴリズムとして利用することができるのでPはNPに含まれる。

決定アルゴリズムの時点で速度が十分ある(任意の問題を多項式時間で決定できる)場合は決定アルゴリズムをそのまま証明検証アルゴリズムに流用することができる。決定アルゴリズムを使った検証では#cが不要になる。(前回エントリより)

よってNP ⊇ Pという包含関係が成り立つ。ただしこの包含関係が真部分集合であるかどうかは30年以上前からの重大な未解決問題(P ≠ NP予想)になっている。

Pが見つかっていないNPとNP完全

NPである問題に多項式時間アルゴリズムが見つかれば、その問題はPに分類することができる。

NP完全といわれるNP中の特殊なクラスの場合は少し話が違っていてPで解けるアルゴリズムが見つかった場合は全てのNP問題がPで解けるという、ある種革命的な状況が発生してしまう(P=NP)。

これ以外のNP問題、つまり現状でNP完全なのかPなのか分かっていない問題はNP-intermediateと言われている

en.wikipedia.org

ただしP=NPが判明すればNPIは空集合になる。P ≠ NPの場合はNPIが存在する。PapadimitriouのComputational Complexityにこのクラスの存在証明が乘っているらしい。

ぼくには簡単ではありませんが (^^;) Papadimitriou の Computational Complexity に証明が載っていました。対角線論法を使ってうまいこといったはず。

srad.jp

Computational Complexity

Computational Complexity

  • 作者: Christos H. Papadimitriou
  • 出版社/メーカー: Addison Wesley
  • 発売日: 1993/11/30
  • メディア: ペーパーバック
  • 購入: 1人 クリック: 1回
  • この商品を含むブログを見る

実際に本を確認してみたところ、以下の記述がそれらしい

Theorem 14.1: IF P ≠ NP, then there is a language in NP which is neither in P nor is it NP-complete(p330)

Theoremのあとに証明が続くが割愛

Papadimitriouの本以外にも以下の本にもNPIの章と証明はあった

Computational Complexity: A Modern Approach

Computational Complexity: A Modern Approach

どの本に乗っている証明も以下の論文の引用になっていた

  • Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility".

素因数分解やグラフ同型問題が今の所、このクラスだろうと考えられている

ちなみに多くの専門家はP=NPではないと予想している。(2012年時点で126/152人)

http://dopal.cs.uec.ac.jp/okamotoy/PDF/2013/complexity10confusions.pdf

*1:Nondeterministicの一般定義というのはないと思うので、あくまで業務システムに触れることが多い一個人の感想です。

*2:NPの定義が「多項式時間で検証できる」という分かりやすい書き方になっていない理由は後続エントリのnon-deterministicを扱う際に重要になる