正しい問題を選ぶ

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

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