3
$\begingroup$

In Computational Complexity -- A Modern Approach, by Arora and Barak, they have the following claim (Example 3.6).

Let EXPCOM be the following language $$ \{ \langle M, x, 1^n\rangle \mid M \text{ outputs 1 on $x$ within $2^n$ steps} \} $$ Then $\mathbf{P}^{\mathrm{EXPCOM}} = \dots = \mathbf{EXP}$. [...]

Clearly, an oracle to EXPCOM allows one to perform an exponential-time computation at the cost of one call, and so $\mathbf{EXP} \subseteq \mathbf{P}^{\mathrm{EXPCOM}}$. [...]

I believe their reasoning is as follows:

  1. Suppose we have a language $L \in \mathbf{EXP}$.

  2. Thus there is a TM $M$ that decides it in time $2^{n^c}$.

  3. We want to create a poly-time oracle-TM $T^{\mathrm{EXPCOM}}$ that decides $L$.

  4. $T$ works as follows on input a string $x \in \{ 0, 1 \}^{*}$. It queries its EXPCOM oracle on input $\langle M, x, 1^{n^c} \rangle $, and outputs the same answer as the oracle.

  5. Clearly $T$ runs in polynomial time, and it decides the same language as $M$. QED.

Here is my confusion. For $T$ to call its EXPCOM oracle, it needs to know which $M$ that decides $L$ (in exponential time). However, 2. only promises the existence of a machine $M$; it doesn't actually tell you how to find it! (this problem also applies to the running time $2^{n^c}$ of $M$).

So clearly I'm misunderstanding something, but what? Is it my understanding of the language EXPCOM? Is it my description of $T$? Or have I misunderstood oracle-TMs altogether? (Or maybe all three?)

$\endgroup$
1
$\begingroup$

You are correct that $T$ needs to know which Turing machine accepts $L$. This Turing machine is $M$, and you can hardcode it into $T$. There is absolutely no problem with that.

Here is a similar example. Suppose that there is a proof that $P \neq NP$. Then there is a Turing machine that prints a proof of $P \neq NP$.

Proof: According to the assumption, there is a proof $\pi$ that $P \neq NP$. Construct a Turing machine $T$ that prints $\pi$. Then $T$ prints a proof of $P \neq NP$. $\quad\square$

What seems to worry you is that you think of $T$ as accepting $L$ as an input, from which it is supposed to come up with the Turing machine $T$. But this is not the case – all we have to do is to show that for each $L$ there exists an appropriate Turing machine $T$. Moreover, it is not clear how $T$ would accept $L$ as input – a language is, in general, an infinite object.


Sometimes we do need to be worried about the issue that you raised. Here is an example. Let $L_1,L_2,\dots$ be an infinite sequence of decidable languages. For each $L_i$, there is a Turing machine $T_i$ that decides $L_i$. But is there a Turing machine $T$ that accepts an index $i$ and a word $w$ and returns whether $w \in L_i$? Not necessarily (I'll let you come up with a counterexample). When such a machine $T$ does exist, we say that $L_1,L_2,\dots$ are uniformly decidable.

No such uniformity condition appears in your question. We could impose such a condition artificially by providing $L$ as an input via a Turing machine, not necessarily running in exponential time, that accepts $L$. In this case, your criticism would be valid – given a Turing machine that accepts a language in $\mathsf{EXP}$, it is not clear how to find a Turing machine accepting the same language and running in exponential time.

$\endgroup$
  • $\begingroup$ I didn't mean that $T$ takes $L$ as input no. Regarding your counter-example question, I guess the issue is that it gives you the ability to solve undecidable problems like the halting problem? (e.g., let $L$ be the unary language where $1^i \in L$ iff $M$ halts on input $x$ where $i$ encodes TM $M$ and input $x$. $L$ can be accepted by non-uniform TMs of course) $\endgroup$ – panto Sep 16 '18 at 18:02
  • $\begingroup$ My counterexample asks for a sequence of decidable languages $L_1,L_2,\ldots$ such that the language $\{(i,x) : x \in L_i\}$ is not decidable. $\endgroup$ – Yuval Filmus Sep 16 '18 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.