# Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak

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?)

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.

• 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) Sep 16, 2018 at 18:02
• 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. Sep 16, 2018 at 23:02