多項式時間、NP問題など

こちらより理解メモ

• 解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現出来るものが存在するアルゴリズムを、多項式時間のアルゴリズムという
• ここでも少し触れていた
• 決定性の多項式時間アルゴリズムでと受ける判定問題の集合をクラスPと呼ぶ。

その上で、これとこれを読んだ

• 非決定性チューリングマシンによって多項式時間で解くことが出来る問題をクラスNPという。
• NP完全問題とは、クラスNPに属する問題かつ、クラスNPのすべての問題から多項式時間帰着可能な問題のこと。
• NP困難とは、NPに属する問題と比べ、同等以上に難しいということ。