两个定义:

  • NP 是一组决策问题,可由非确定性图灵机在多项式时间内求解。
  • NP 是一组决策问题,可由确定性图灵机在多项式时间内进行验证。