在恒定时间内可以解决的问题属于P问题的类别



示例:确定4/2的值,这是O(1(问题。据我所知,可以在多项式时间内解决的任何问题都属于P问题的类别。因此,它也应该属于这一类,因为根据我的说法,在多项式时间内可以说可以解决任何可以解决的问题。

当我们说"多项式时间"时,我们的意思是o(n^c(。o(x(代表" x或更少",因此恒定时间也属于此类别。答案"在多项式时间内可在恒定时间内解决问题吗?"是是的。我们还说,"在恒定时间内解决问题属于P问题类别的答案?"是的。

但是,您的示例"确定4/2的值"不是P问题。P问题被定义为"复杂性P类是所有决策问题的集合,可以通过最差的多项式时间复杂性来解决"。决策问题的"是"或"否"为输出,而不是2。另外,这样的问题应该具有输入。问题的决定变体可能是:

给定三个数字A,B和C,确定A/B&LT是否;C。为此,任何算法都需要在最坏情况下检查输入的所有位,因此它将不再是恒定的算法了。问题仍在p。

在恒定时间中可解决的问题通常在复杂性理论中是没有用的,因为我们甚至无法在恒定时间内检查输入的每一点。

一个(无用的(恒定时间决策问题的示例(因此,p(为:

给定的n输入号,确定4/2 =2。输出不取决于输入,并且始终是是。

(无用的(恒定时间决策问题的另一个示例(p(为:

给定一个数组a,确定a [0]是否均匀。

最新更新