I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working through the material and trying to explain it as well I can.


Now, I think I have a reasonably grasp of the Baker–Gill–Solovay Theorem. The basic construction that everybody seems to use is this:

Construct a language $B$ iteratively for $i = 0, 1, 2, \ldots$ by picking a number $n \geq i$ such that we have not looked at strings of length ${\geq}\, n$ before. Then simulate $M_i$ on input $2^n$ for $2^n/10$ steps. Answer each of its oracle queries negatively unless we answered it positively in the past. If $M_i$ halts with acceptance, decide that $B \cap \{0,1\}^n = \emptyset$. If it halts with rejection, decide that $B\cap \{0,1\}^n$ consists exactly of those strings of length $n$ that $M_i$ did not query.


What I don't understand is why we simulate $M_i$ for $2^n/10$ steps.

  • The first thing that caught my eye is the oddly specific constant $10$. Is this important? Why not e.g. $2^n/2$?
  • Wouldn't $2^n-1$ or even $2^n$ also work? After all, if $M_i$ takes that much time it is ‘harmless’ anyway.
  • In fact, why not just forgo the simulation altogether and simply say: no matter how long it takes, if $M_i$ accepts $2^n$ (with all queries of length $n$ answered negatively) we pick $B \cap \{0,1\}^n = \emptyset$ and otherwise set $B\cap\{0,1\}^n$ to all strings of size $n$ that $M_i$ does not query for input $1^n$.

As far as I see it, the argument still goes through: if $M$ is a deterministic Turing machine with a $B$ oracle running in time $f(n)$ with $f(n)\in o(2^n)$, then there are $i$, $n$ such that $M_i = M$ and $f(n) < 2^n$ and thus $M$ cannot query all strings of length $n$ for input $1^n$ and consequently gives the wrong answer for input $1^n$.

Edit: I think I just understood why we need to put at least some bound on the simulation of $M_i$. Otherwise there could be a machine that runs forever and queries all strings in $\{0,1\}^*$ and then we have nothing more to choose from. But I still don't see why $2^n$ steps instead of $2^n/10$ shouldn't work.

  • $\begingroup$ $2^n-1$ time would also be fine. If the deterministic machine can make $2^n$ oracle calls, then it can indeed decide the language that is used in the separation, and hence the claim we are trying to prove, that the language cannot be decided by a deterministic algorithm with a given running time, is false. $\endgroup$ May 16, 2023 at 20:23
  • $\begingroup$ If you read some French, you can have a look at the proof in the book by Perifel (irif.fr/_media/users/sperifel/complexite.pdf, théorème 7-AA) where there is no "$2^n/10$." I find this proof less magical than others. (If you don't read French, probably automatic translation can help.) $\endgroup$
    – Bruno
    May 17, 2023 at 6:59
  • $\begingroup$ @RobinKothari: I don't know, I'm still convinced that any finite number of steps of simulation would be fine: yes, a machine that can make $2^n$ oracle calls can decide the language, but that isn't an issue. Such a machine clearly takes $\Omega(2^n)$ time and such we can simply ignore it altogether in our considerations. The only thing we have to make sure is that we don't simulate the machine forever and query strings of all lengths, because then we won't have any more choices to make for the next machine. $\endgroup$ May 17, 2023 at 8:31
  • $\begingroup$ (any finite number of steps that is at least exponential in $n$, of course; or if we only care about $\text{P}^B\neq \text{NP}^B$ then something like $n^i + i$ should also work) $\endgroup$ May 17, 2023 at 9:22
  • 1
    $\begingroup$ The point is how to enumerate TMs that run in polynomial time. This is explained in Remarque 3-AL: from any enumeration $(M_i)_i$, construct for all $i$ a new machine $M'_i$ that has (on an extra tape) a counter of the number of steps, and stops after $i+n^i$ steps ($n=$ input size). Then $(M'_i)_i$ is an enumeration of TMs running in polynomial time. You can do this for any enumeration $(M_i)_i$, in particular when the $M_i$'s are oracle TMs. $\endgroup$
    – Bruno
    May 17, 2023 at 12:04


Your Answer

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