#581. NOIP2012TG-20

NOIP2012TG-20

  1. (不定项选择题,正确答案数 ≥ 1)以下关于计算复杂度的说法中,正确的有( )。

{{ multiselect(1) }}

  • 如果一个问题不存在多项式时间的算法,那它一定是 NPNP 类问题
  • 如果一个问题不存在多项式时间的算法,那它一定不是 PP 类问题
  • 如果一个问题不存在多项式空间的算法,那它一定是 NPNP 类问题
  • 如果一个问题不存在多项式空间的算法,那它一定不是 PP 类问题