正しい問題を選ぶ

問題の NP 困難性を証明するうえで最も難しいステップの一つは、帰着元となるのに適した問題を選ぶ部分です。Cook-Levin の定理からは、ある NP 困難な問題から問題 \(X\) への帰着があるならば、任意の NP 困難な問題から問題 \(X\) への帰着が存在することが言えます。しかしそうは言っても帰着のしやすさは問題によって異なります。問題を選ぶ機械的な方法というのは存在しませんが、役に立つであろう経験則をいくつかあげます:

• 問題がオブジェクトにビットを割り当てたり、集合の部分集合を選んだり、集合を二つに分割したりしていたら、\(\textsc{SAT}\) あるいは \(\textsc{Partition}\) の何らかのバージョンからの帰着を試してみる。

• 問題がラベル (大きさが固定の小さな集合から選ぶもの) を割り当てたり、集合を小さな部分集合に分割していたら、\(k \textsc{Color}\) あるいは \(\textsc{3Color}\) からの帰着を試してみる。

• 問題が何かを特定の順番に並べていたら、\(\textsc{DirectedHamCycle}\) や \(\textsc{Directed}\)\(\textsc{HamPath}\) あるいは \(\textsc{TravelingSalesman}\) からの帰着を試してみる。

• 問題が何らかの制約を満たす大きな部分集合を見つけようとしていたら、\(\textsc{MaxIndSet}\), \(\textsc{MaxClique}\), \(\textsc{Max2SAT}\) からの帰着を試してみる。

• 問題が集合をたくさんの小さな部分集合へと分割しようとしていたら、\(\textsc{3Partition}\) からの帰着を試してみる。

• 問題に \(3\) という数字が自然に出現するなら、\(\textsc{3SAT}\), \(\textsc{3Color}\), \(\textsc{X3M}\), \(\textsc{3Partition}\) からの帰着を試してみる (ふざけてなんかいません)。

• どれもダメだったら、\(\textsc{3SAT}\) あるいは \(\textsc{CircuitSAT}\) だって試す！

\(\textsc{Tetris}\) あるいは \(\textsc{SuperMarioBros}\) または \(\textsc{TrainYard}\) を帰着元として使うのはお勧めしません。あなたが選ぶべきなのは、問題を難しくしている何らかの特徴を捉えながらもできるだけ単純であるような問題です。