0
$\begingroup$

I know that there is no way to prove that P = NP, but how would one go about proving constant time /= P (i.e. O(1) /= POLY(n))?

(Or perhaps that any two other complexity classes do not equal each other).

If anyone has any papers on this, that would be really helpful :).

$\endgroup$
5
  • 1
    $\begingroup$ The time hierarchy theorem implies this, there is a proof on wikipedia. $\endgroup$
    – plshelp
    Jun 11, 2023 at 14:09
  • 2
    $\begingroup$ Why do you claim that "there is no way to prove that P = NP"? Even that would be an amazing result... $\endgroup$
    – Steven
    Jun 11, 2023 at 15:35
  • $\begingroup$ The wikipedia page also shows the correct notation. While $O(1) \ne poly(n)$ (meaning that the sets of functions are not equal), this is not the statement that you want. $\endgroup$
    – Dmitry
    Jun 11, 2023 at 20:15
  • $\begingroup$ Any problem the solution of which depends on all elements of the input takes time at least $O(n)$ to be aware of the input thus cannot be solved in $O(1)$. $\endgroup$
    – user16034
    Jun 12, 2023 at 6:54
  • $\begingroup$ @Steven I'd guess deciding $A\stackrel{?}{=}B$ for arbitrary classes is undecidable. I don't think a particular instance can be proven undecideable just as how there are no uncomputable individual busy beaver numbers. $\endgroup$
    – rus9384
    Jun 12, 2023 at 8:34

1 Answer 1

0
$\begingroup$

Take the problem of determining whether the input, a natural represented as a binary string, is an even natural.

This can easily be solved by a TM in $O(N)$: just go to the end of the input and check the last bit. (Note that $N$ here is the length of the input string.)

This problem can not be solved in $O(1)$. By contradiction, assume that a TM does solve it in $k$ steps for any given constant $k$. Then, take any input that's longer than $k$. The TM starts on the first bit and in $k$ moves can not reach the last bit, so it have to give the same result for an even and an odd input number. Hence it does not solve the problem.

This reasoning can be generalized to prove that the problems solvable in $O(1)$ are strictly included in those solvable in $O(f(N))$ with unbounded $f$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.