最終更新:2016-06-02 (木) 00:11:30 (2879d)  

NP
Top / NP

Non-deterministic Polynomial

ある解候補が与えられたとき、それが本当に解であるかどうかを多項式時間で確認できる問題の集合

関連

  • NP困難 - NPに属するどの問題よりも同程度以上に難しい問題のこと
  • NP完全? - NP困難であって、かつNPに属する問題のこと
  • 多項式時間還元?
  • SAT? - 充足可能性問題?



検索：