# How to prove O(1) /= POLY(n)?

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 :).

• The time hierarchy theorem implies this, there is a proof on wikipedia. Jun 11, 2023 at 14:09
• Why do you claim that "there is no way to prove that P = NP"? Even that would be an amazing result... Jun 11, 2023 at 15:35
• 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. Jun 11, 2023 at 20:15
• 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)$.
– user16034
Jun 12, 2023 at 6:54
• @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. Jun 12, 2023 at 8:34

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$$.