# Is SAT in P^{SAT}?

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?

-
The source of the confusion is that complexity theorists have to be more careful with I/O conventions that computability theorists. In classical computability theory, efficiency isn't a consideration, which leads to robustness against many variations in the definitions. In complexity theory, small changes in the input/output conventions can turn a P-time function into a non-P-time function or vice-versa. So one has to be careful about using computability sources when studying complexity. The Wikipedia article shows what can happen from mixing the fields by using definitions out of context. –  Carl Mummert Sep 1 '11 at 21:02

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:

2. Copy the input onto the oracle tape. This takes $O(n)$ time, where $n$ is the length of the input.
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}$.