# Looking for a problem provably not in P

My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. Papadimitriou basically says that the proof is very similar to that of Cook-Levin theorem and do it yourself. Also, I wish to see the paper why Checkers is EXP-complete, but couldn't find a free version on the net.

Can you show me why a problem can be EXP-complete and not in P provably? How is the diagonalization encoded in the problem instances?

• Isn't the time hierarchy theorem exactly what you are looking for? Any EXP-hard problem would do. Commented Aug 24, 2018 at 8:52
• "My basic position is that everything is in P." What do you mean by that? Commented Sep 30, 2018 at 18:38

The time hierarchy theorem already does the diagonalization for you.

Let $X$ be any $\mathbf{EXP}$-complete problem. If $X\in\mathbf{P}$, then $\mathbf{EXP}=\mathbf{P}$, since we can solve any problem in $\mathbf{EXP}$ by using the polynomial-time reduction to $X$ followed by the polynomial-time algorithm for $X$. But $\mathbf{EXP}=\mathbf{P}$ contradicts the time hierarchy theorem, because that tells us that there are problems in $\mathbf{EXP}$ that are not in $\mathbf{P}$. Therefore, $X\notin\mathbf{P}$ for any $\mathbf{EXP}$-complete $X$.

Honestly, the proof that checkers is $\mathbf{EXP}$-complete will be long and not at all enlightening: the only thing that simulating Turing machines with checkers positions will teach you is that the craziest systems can support computation. It's much easier to see that the following problem is $\mathbf{EXP}$-complete. The input is the description of a Turing machine $M$, and an input $x$. You accept if $M(x)$ halts within $2^{|x|}$ steps and reject otherwise. Call the language of accepted strings $L$.

So, let $Y\in\mathbf{EXP}$ be a set of strings over, e.g., $\{0,1\}^*$. It is decided by a Turing machine $M$ that runs in at most $2^{n^c}$ steps for some integer constant $c$, on inputs of length $n$. We define a new Turing machine $M'$ with input alphabet $\{0,1,p\}$ ("$p$" for "pad") that behaves as follows:

• if its input is of the form $z\,p^{|z|^c-|z|}$ for some $z\in\{0,1\}^*$, it simulates $M(z)$ and accepts or rejects as that machine does;
• otherwise, it rejects.

Note that $|z\,p^{|z|^c-|z|}| = |z|^c$.

Now, the reduction of $Y$ to $L$ is as follows. Given a string $y\in\{0,1\}^*$ for which we want to know whether $y\in Y$, we ask whether $(\langle M'\rangle, y\,p^{|y|^c-|y|})\in L$. We can construct this query in polynomial time, since the description of $M'$ is some constant string, and we just need to write an easily computed polynomial number of $p$'s after $y$. And we have $(\langle M'\rangle, y\,p^{|y|^c-|y|})\in L$ iff $M'$ accepts $y\,p^{|y|^c-|y|}$ in at most $2^{|y\,p^{|y|^c-|y|}|}=2^{|y|^c}$ steps, iff $M$ accepts $y$ in at most $2^{|y|^c}$ steps, iff $y\in Y$.

Similar techniques give you complete problems for any time or space complexity class.

• I wonder where you learnt this. Commented Aug 24, 2018 at 12:59
• @ZiruiWang Not sure, sorry. I've known for a long time that "Does this Turing machine accept or reject its input within the resource bounds of $C$" is $C$-complete for most "reasonable" complexity classes $C$. Anyway, glad to be able to pass on the knowledge. :-) Commented Aug 24, 2018 at 13:09