首页 > 试题广场 >

以下关于判定问题难易处理的叙述中正确的是 。

[单选题]
以下关于判定问题难易处理的叙述中正确的是
  • 可以由多项式时间算法求解的问题是难处理的
  • 需要超过多项式时间算法求解的问题是易处理的
  • 可以由多项式时间算法求解的问题是易处理的
  • 需要超过多项式时间算法求解的问题是不能处理的
答案:C.
超过多项式时间算法是难求解的,比如指数时间复杂度,即解决问题的时间是问题规模的指数函数,并不是不能处理的。
不能处理的问题如图灵停机问题。而超过多项式的时间算法并不是不可解的。
多项式时间算法是容易求解的。
发表于 2022-03-07 13:03:24 回复(0)