NP 问题

定义

  • 易解问题 := 多项式复杂度问题 $O(n^{b})$
  • 非易解问题 := $\neg$ 易解问题
  • P 类问题 := 多项式时间 $O(n^{b})$ 内可构造解
  • NP 问题 := $\neg$ P 类问题 = 多项式时间 $O(n^{b})$ 内可验证解