常数时间内可解的问题是否属于 P 类问题？ [解决了]
Does problems solvable in constant time fall under the category of P problems? [SOLVED]
例子：确定4/2的值，这是一个O(1)的问题。据我所知，任何可以在多项式时间内解决的问题都属于 P 类问题。因此它也应该属于这一类，因为根据我的说法，任何可以在常数时间内解决的问题都可以说是在多项式时间内可以解决的。
当我们说 "Polynomial time" 时，我们的意思是 O(n^c)。 O(x)代表"x or less"，所以常数时间也属于这一类。 "Are problems solvable in constant time solvable in polynomial time?" 的答案是肯定的。我们还说 "Do problems solvable in constant time fall under the category of P problems?" 的答案是肯定的。
但是，您的示例 "determining the value of 4/2" 在技术上不是 P 问题。 P 问题定义为 "The complexity class P is the set of all decision problems that can be solved with worst-case polynomial time-complexity"。一个决策问题有 "yes" 或 "no" 作为输出，而不是 2。此外，这样的问题应该有一个输入。您的问题的决策变体可能是：
给定三个数字 a、b 和 c，确定是否 a/b < c。为此，任何算法都需要在最坏的情况下检查输入的所有位，因此它不再是 constant-time 算法。问题还在P.
在常数时间内可解的问题在复杂性理论中通常是无用的，因为我们甚至无法在常数时间内检查输入的每一位。
一个（无用的）constant-time 决策问题的例子（所以在 P 中）是：
给定 n 个输入数字，判断是否 4 / 2 = 2。输出不依赖于输入且始终为是。
另一个（无用的）constant-time 决策问题的例子（所以在 P 中）是：
给定一个数组 A，判断 A[0] 是否为偶数。
例子：确定4/2的值，这是一个O(1)的问题。据我所知，任何可以在多项式时间内解决的问题都属于 P 类问题。因此它也应该属于这一类，因为根据我的说法，任何可以在常数时间内解决的问题都可以说是在多项式时间内可以解决的。
当我们说 "Polynomial time" 时，我们的意思是 O(n^c)。 O(x)代表"x or less"，所以常数时间也属于这一类。 "Are problems solvable in constant time solvable in polynomial time?" 的答案是肯定的。我们还说 "Do problems solvable in constant time fall under the category of P problems?" 的答案是肯定的。
但是，您的示例 "determining the value of 4/2" 在技术上不是 P 问题。 P 问题定义为 "The complexity class P is the set of all decision problems that can be solved with worst-case polynomial time-complexity"。一个决策问题有 "yes" 或 "no" 作为输出，而不是 2。此外，这样的问题应该有一个输入。您的问题的决策变体可能是：
给定三个数字 a、b 和 c，确定是否 a/b < c。为此，任何算法都需要在最坏的情况下检查输入的所有位，因此它不再是 constant-time 算法。问题还在P.
在常数时间内可解的问题在复杂性理论中通常是无用的，因为我们甚至无法在常数时间内检查输入的每一位。
一个（无用的）constant-time 决策问题的例子（所以在 P 中）是：
给定 n 个输入数字，判断是否 4 / 2 = 2。输出不依赖于输入且始终为是。
另一个（无用的）constant-time 决策问题的例子（所以在 P 中）是：
给定一个数组 A，判断 A[0] 是否为偶数。