<h5>Context</h5>
<p>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.</p>
<h5>Setting</h5>
<p>Now, I think I have a reasonably grasp of the Baker–Gill–Solovay Theorem. The basic construction that everybody seems to use is this:</p>
<p>Construct a language <span class="math-container">$B$</span> iteratively for <span class="math-container">$i = 0, 1, 2, \ldots$</span> by picking a number <span class="math-container">$n \geq i$</span> such that we have not looked at strings of length <span class="math-container">${\geq}\, n$</span> before. Then simulate <span class="math-container">$M_i$</span> on input <span class="math-container">$2^n$</span> for <span class="math-container">$2^n/10$</span> steps. Answer each of its oracle queries negatively unless we answered it positively in the past. If <span class="math-container">$M_i$</span> halts with acceptance, decide that <span class="math-container">$B \cap \{0,1\}^n = \emptyset$</span>. If it halts with rejection, decide that <span class="math-container">$B\cap \{0,1\}^n$</span> consists exactly of those strings of length <span class="math-container">$n$</span> that <span class="math-container">$M_i$</span> did not query.</p>
<h5>Question</h5>
<p>What I don't understand is why we simulate <span class="math-container">$M_i$</span> for <span class="math-container">$2^n/10$</span> steps.</p>
<ul>
<li>The first thing that caught my eye is the oddly specific constant <span class="math-container">$10$</span>. Is this important? Why not e.g. <span class="math-container">$2^n/2$</span>?</li>
<li>Wouldn't <span class="math-container">$2^n-1$</span> or even <span class="math-container">$2^n$</span> also work? After all, if <span class="math-container">$M_i$</span> takes that much time it is ‘harmless’ anyway.</li>
<li>In fact, why not just forgo the simulation altogether and simply say: no matter how long it takes, if <span class="math-container">$M_i$</span> accepts <span class="math-container">$2^n$</span> (with all queries of length <span class="math-container">$n$</span> answered negatively) we pick <span class="math-container">$B \cap \{0,1\}^n = \emptyset$</span> and otherwise set <span class="math-container">$B\cap\{0,1\}^n$</span> to all strings of size <span class="math-container">$n$</span> that <span class="math-container">$M_i$</span> does not query for input <span class="math-container">$1^n$</span>.</li>
</ul>
<p>As far as I see it, the argument still goes through: if <span class="math-container">$M$</span> is a deterministic Turing machine with a <span class="math-container">$B$</span> oracle running in time <span class="math-container">$f(n)$</span> with <span class="math-container">$f(n)\in o(2^n)$</span>, then there are <span class="math-container">$i$</span>, <span class="math-container">$n$</span> such that <span class="math-container">$M_i = M$</span> and <span class="math-container">$f(n) &lt; 2^n$</span> and thus <span class="math-container">$M$</span> cannot query all strings of length <span class="math-container">$n$</span> for input <span class="math-container">$1^n$</span> and consequently gives the wrong answer for input <span class="math-container">$1^n$</span>.</p>
<p><strong>Edit:</strong> I think I just understood why we need to put at least <em>some</em> bound on the simulation of <span class="math-container">$M_i$</span>. Otherwise there could be a machine that runs forever and queries all strings in <span class="math-container">$\{0,1\}^*$</span> and then we have nothing more to choose from. But I still don't see why <span class="math-container">$2^n$</span> steps instead of <span class="math-container">$2^n/10$</span> shouldn't work.</p>

CC BY-SA 4.0
2023-05-16T20:23:18.437Z
$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.
Robin Kothari
CC BY-SA 4.0
2023-05-17T06:59:24.883Z
If you read some French, you can have a look at the proof in the book by Perifel (https://www.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.)
Bruno
CC BY-SA 4.0
2023-05-17T08:31:58.977Z
@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.
Manuel Eberl
CC BY-SA 4.0
2023-05-17T09:22:35.727Z
(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)
Manuel Eberl
CC BY-SA 4.0
2023-05-17T09:45:05.273Z
@Bruno: I do have one issue with that proof: in the beginning they say that $M_i$ is an enumeration of all polynomial-time oracle machines. But what does that even mean? Does that mean that these machines have to run in polynomial time no matter what oracle you give them? That would seem to strong to me. One could easily imagine a DTM that decides some language $X$ in polynomial time given the right oracle but runs forever if you give it the "wrong" oracle.
Manuel Eberl
CC BY-SA 4.0
2023-05-17T12:04:49.697Z
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.
Bruno
CC BY-SA 4.0
2023-05-17T12:32:06.550Z
Okay, that makes sense. Thanks! I can see how that would simplify the construction. It essentially "factors out" the awkward thing about having to "guess" how long the machine will take and requiring that each machine has an infinite number of representations.
Manuel Eberl
<cc.complexity-theory><complexity-classes><time-complexity><turing-machines>
Baker–Gill–Solovay Theorem: why $2^n/10$ steps?
Manuel Eberl
# Baker–Gill–Solovay Theorem: why $2^n/10$ steps?

(Asked by: username_0 on 2023-05-16)

##### Context

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.

##### Setting

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.

##### Question

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.

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, turing-machines
> **Comments:**
> **username_1**: $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.  
> **username_2**: If you read some French, you can have a look at the proof in the book by Perifel (https://www.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.)  
> **username_0**: @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.  
> **username_0**: (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)  
> **username_0**: @Bruno: I do have one issue with that proof: in the beginning they say that $M_i$ is an enumeration of all polynomial-time oracle machines. But what does that even mean? Does that mean that these machines have to run in polynomial time no matter what oracle you give them? That would seem to strong to me. One could easily imagine a DTM that decides some language $X$ in polynomial time given the right oracle but runs forever if you give it the "wrong" oracle.  
> **username_2**: 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.  
> **username_0**: Okay, that makes sense. Thanks! I can see how that would simplify the construction. It essentially "factors out" the awkward thing about having to "guess" how long the machine will take and requiring that each machine has an infinite number of representations.  

---

## 0 answers

