Search code examples
time-complexitycomplexity-theory

Does problems solvable in constant time fall under the category of P problems?


example: determining the value of 4/2, which is an O(1) problem. As far as I know, any problem which can be solved in a polynomial time fall under the category of P problems. Hence it should also fall under this category, since according to me any problem which can be solved in constant time can be said as solvable in polynomial time.


Solution

  • When we say "Polynomial time" we mean O(n^c). O(x) stands for "x or less", so constant time also falls in this category. The answer to "Are problems solvable in constant time solvable in polynomial time?" is Yes. We also say that the answer to "Do problems solvable in constant time fall under the category of P problems?" is Yes.

    However, your example "determining the value of 4/2" is technically not a P problem. P problems are defined as "The complexity class P is the set of all decision problems that can be solved with worst-case polynomial time-complexity". A decision problem has "yes" or "no" as output, not 2. Also, such a problem should have an input. The decision variant of your problem might be:

    Given three numbers, a, b and c, determine if a/b < c. For this, any algorithm needs to check all bits of the input in the worst case, so it wouldn't be a constant-time algorithm anymore. The problem is still in P.

    Problems solvable in constant time are often useless in complexity theory, because we can't even check every bit of the input in constant time.

    An example of a (useless) constant-time decision problem (so in P) is:

    Given n input numbers, determine if 4 / 2 = 2. The output does not depend on the input and is always yes.

    Another example of a (useless) constant-time decision problem (so in P) is:

    Given an array A, determine if A[0] is even.