[Math] Is SAT in P^{SAT}

computational complexity

I'm trying to wrap my head around relativization in non-Turing machine settings (for example, what is the "natural" relativized version of Graph Isomorphism to an oracle A?).

So I went to Wikipedia to look up relativization, and it gave me the standard oracle machine definition — a Turing machine, with a work tape and an oracle tape containing the characteristic function of your oracle set A. Each timestep it will read a symbol off of each tape, write a symbol on the work tape, then move left/right on each tape separately (and change states). Then it starts talking about relativized versions of complexity classes, specifically mentioning P^{SAT}.

Here is my problem with their definition: You now pass your oracle Turing machine an instance of SAT of "size" n and ask it if it has a solution. The machine computes some canonical encoding of this instance as an integer M, and looks up M in the oracle tape. If the oracle tape has a 1 in space M, the instance is satisfiable. If not, it is not.
However! The number of SAT instances of size n grows exponentially as a function of n, so M is of exponential size and getting to location M on the oracle tape takes exponential time.

So if one uses the naive algorithm for the SAT oracle machine, one finds that solving SAT takes exponential time, and SAT is not in P^{SAT}!!!

What am I missing?

Best Answer

Let's go to a more reliable source than Wikipedia: the first edition of Sipser's Introduction to the Theory of Computation. I quote directly from definition 9.16 on page 318:

An oracle is a language A. An oracle Turing machine $M^{A}$ is an ordinary Turing machine with an extra tape called the oracle tape. Whenever M writes a string on the oracle tape it is informed whether that string is a member of A, in a single computation step.

Note that the stipulation of the single computation step is a critical part of the definition. We can use this definition to answer your question. Let's say we have a Turing machine M with an oracle for SAT. We can use it to show that SAT is in $P^{SAT}$ as follows:

  1. We start with the input for the SAT instance already on M.
  2. Copy the input onto the oracle tape. This takes $O(n)$ time, where $n$ is the length of the input.
  3. M is informed of the result. This takes 1 step, by the definition above.
  4. M returns this result as its answer. This takes $O(1)$ time.

So the total time is linear, which is still polynomial time. So SAT is indeed in $P^{SAT}$.

Related Question