停止性問題はNP困難

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

　昨年秋に購入し，Union-Find（第11章）は面白いな，講義かプログラミング科目で使えないかなと，そのときは思ったものの，忘れてしまっていました．
　先日，横積みになった中からこの本を開いて読み直すと，PとNPの章（第17章）で，停止性問題がNP困難であるであると書かれていて，起き上がってじっくり読みました．まずはNP困難の定義から(p.321)．

NP困難
　問題Xに対し，あるNP完全問題Yが存在して，Xが多項式時間アルゴリズムで解けるならばYも多項式時間アルゴリズムで解けるとき，XはクラスNP困難(class NP-hard)に属するといいます．また，NP困難に属する問題をNP困難問題といいます．

　NP完全を使用することなく，NP困難*1を定義し，NP完全はNPに属しかつNP困難であると定義することも可能ですが，上の定義にしたのは，本書では先にP，NP，NP完全を定義していたためと，読むことができます．
　紙面を1枚めくると，停止性問題の話です．この問題の定義と，これがNP困難であることは，p.323に書かれています．

停止性問題
　コンピュータプログラムPと，そのプログラムへの入力Iが与えられます．Iを入力としてPを実行したとき，Pが有限時間で停止するかどうかを判定してください．

　停止性問題がNP困難に属することは容易に示すことができます．停止性問題を解く多項式時間アルゴリズムHが存在するならば，充足可能性問題(SAT)を多項式時間で解けることを示します．「論理式を入力として受け取り，もしそれを充足する真理値割当が存在するならばそれを出力し，存在しないならば無限ループに陥るようなプログラム」を考えます．このプログラムと論理式をHに入力すると，それが有限時間で停止するかどうかを多項式時間で判定することができます．これは，与えられた論理式を充足する真理値割当が存在するかを多項式時間で判定できることを意味します．以上から，停止性問題がNP困難に属することが示されました．
　一方，停止性問題は，実はそもそも「解くことのできない問題」であることが知られており，NPには属しません．具体的には，停止性問題を解くことのできるプログラムが存在すると仮定して，矛盾を導くことができます．(以下略)

　上の文書で，明記されていないけれど注意したいことが，2つあります．まず，「停止性問題を解く多項式時間アルゴリズムHが存在すること」は証明しなくてもよいのです．NP困難の定義にある「問題Xに対し，あるNP完全問題Yが存在して，Xが多項式時間アルゴリズムで解けるならばYも多項式時間アルゴリズムで解ける」について，ここでは問題Xは停止性問題，NP完全問題YはSAT，「Xが多項式時間アルゴリズムで解けるならば」の部分は「Hが存在するならば」に，それぞれ対応すると，考えればいいのです．
　もう一つの注意点は，「論理式を入力として受け取り，もしそれを充足する真理値割当が存在するならばそれを出力し，存在しないならば無限ループに陥るようなプログラム」のところです．この仕様を満たすプログラムは，容易に考えつきます．そして，そのプログラムは，多項式時間アルゴリズムでなくてもいいのです．
　実際，入力となる論理式にn個の変数が出現するとき，各変数への（独立した）真偽値の割り当て---全部で2のn乗通り---を順に用意して，論理式の真偽判定を行い，充足する割り当てがあるか否かを判定するという，鈍くさい方法*2でもいいのです．1回の論理式の真偽判定が定数時間であるとしても，すべて試すのに要する時間は指数時間となります．
　このプログラムは，指数時間を要しても，また無限ループを含んでいても，「停止性問題を解く多項式時間アルゴリズムHが存在するならば，充足可能性問題(SAT)を多項式時間で解ける」という主張に影響しない，というわけです．
　ところで，P，NP，NP完全，NP困難は，今年度は第2クォーターで週2コマ×8週で実施した講義科目（ネットワークセキュリティ）で解説しています．ベン図を用いて，NP完全はここ，NP困難はここと，領域を設けています．
　その図では，NP困難な問題のクラスは，決定可能な問題のクラスの部分集合としていました．実際には，上の引用に加え，wikipedia:NP困難にも指摘されているとおり，NP困難だけれど決定可能でない問題が存在するというわけです．次年度の授業の際には，NP困難な問題の領域を，決定可能な問題のクラスの外にも広げるよう，図を修正することにします．

*1:個人的な語感ですが，Xを問題としたとき，「XはNP完全である．」「XはNP困難である．」そして「XはPに属する．」「XはNPに属する．」と表現するのがよく，「XはNP完全に属する．」「XはNP困難に属する．」そして「XはPである．」「XはNPである．」はよくないと考えます．NP-completeとNP-hardは形容詞なのに対し，PとNPは，集合を表す名詞となるからです．

*2:今日の夕食時に，うえの子から「この算数の問題を解いてほしい」と言われて受け取ったのは，ある新聞の切り抜きで，1？2？3？4？5？6？7？8？9の8箇所の？に「＋」「－」「×」「÷」を当てはめ，計算の結果が100になるものを見つけなさいという問題でした．紙面をよく見て，カッコ・カッコ閉じは使わないね，そうだねとやりとりをしたあと，食後にRubyのワンライナーを作成して，解を求めました．演算記号の割り当ては，4の8乗で65536通りとなり，実行時間と，計算の結果が100になったのが何通りかは割愛しますが，一つだけ解を例示すると，「1＋2×3×4×5÷6＋7＋8×9」です．