第 10 回 NP完全問題 本日の内容 10-1. Cook の定理 10-2. 巡回セールスマン問題は NP 完全問題 10-1. Cook の定理 論理式の充足可能性問題は NP 完全である。 論理式の充足可能性問題(SAT: Satisfiability) とは与えられた 論理式を真にするような変数の割当が存在するかどうかを判定する問題です。 これは、変数の割当を非決定的に guess して、実際に論理式に代入して真か どうかを判定できますので、 NP に含まれる問題です。 これが NP 完全問題であることを示すには、NP に含まれるあらゆる問題が SAT に reducible であることを示さなければなりません。 そこで、 素朴な NP 完全問題である CNP を SAT に変換することを考えま す。 つまり、NP に含まれるある問題の入力 x が与えられた時、その問題を解く非