削除された内容 追加された内容
MakoBot (会話 | 投稿記録)
m Robot modifying math category sort key
Sierpinski (会話 | 投稿記録)
32行目:
== NP関連クラスの命名規約について ==
NPに関連するクラスの名称はまぎらわしい。「NP困難」はクラス名に「NP」と付くのに、全てが[[NP]]というわけではない。しかし現状では定着した名称なので、いまさら変わりそうにない。とはいえ、NPを中心に置いた上でそれなりに体系があるのも事実である。
''';NP完全''' — :NPの'''中では'''「完全」な問題を意味する。つまりNPの'''中では'''最も解くのが難しい。 
''';NP困難''' — :「少なくとも」NPと同等以上に難しい問題(ただし、NP'''に属する'''とは限らない)。
''';NP-easy''' — :「たかだか」NPと同等以下しか難しくない問題(ただし、NP'''に属する'''とは限らない)。
''';NP-equivalent''' — :NPと同等に難しい問題(ただし、NP'''に属する'''とは限らない)。
 
== 関連項目 ==