What's wrong with this argument for $NP \ne EXP$?

96 Views Asked by At

Let $\{M_i\}$ be any enumeration of all Turing machines in which each machine appears an infinite number of times.

Consider the language $D = \{i \, | \, M_i(i) \text{ does not accept within }\log(i)^{\log(i)} \text{ steps}\}$. By standard diagonalization arguments, $D \notin P$. Clearly, by simulation, $D \in EXP$.

Now, suppose for the sake of contradiction that $D \in NP$ - that is, there is some way to simulate these machines in $NP$. Consider the related problem $D^{TQBF}$, which is the same language except that $\{M_i\}$ is now an enumeration of Turing machines that can compute relative to $TQBF$ (or any other $PSPACE$-complete problem will do).

Using the same simulation technique, we know that $D^{TQBF} \in NP^{TQBF}$. Using the same diagonalization argument, $D^{TQBF} \notin P^{TQBF}$. But $P^{TQBF} = NP^{TQBF}$. This is a contradiction, so $D \notin NP$.

So $D$ is a problem that is in $EXP$ but not $NP$, so $NP \ne EXP$.


What's wrong with this argument?

1

There are 1 best solutions below

2
On

It seems the problem is in "Using the same simulation technique, we know that $D^{TQBF}\in NP^{TQBF}$". In fact the simulation argument gave you $D\in EXP$ but not directly $D\in NP$ . You have no reason to believe that $D\in NP$ relativises with respect to TQBF.