正しい問題を選ぶ

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

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



Amazon.co.jp アソシエイト (広告)
Audible の無料体験を始めよう
amazon music unlimited で音楽聞き放題
The Art of Computer Programming Volume 1 Fundamental Algorithms
プログラミングコンテストチャレンジブック [第2版]
世界標準MIT教科書 Python言語によるプログラミングイントロダクション
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書