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:
- We start with the input for the SAT instance already on M.
- Copy the input onto the oracle tape. This takes $O(n)$ time, where $n$ is the length of the input.
- M is informed of the result. This takes 1 step, by the definition above.
- 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}$.
A language $L$ is “NP-complete” if $L$ belongs to NP, and every language $X$ in NP can be polynomial-time reduced to $L$; that is the definition of “NP-complete”.
How might we show that every problem $X$ in NP can be reduced to $L$?
Well, $X$ is in NP, and the only thing we have to work with here is the definition of NP:
There is a nondeterministic Turing machine $M$ which,
given a string $I$,
correctly decides in polynomial time
whether $I$ is in $X$.
Cook's theorem takes $M$ and a specific $I$ and constructs a large (but polynomial) family of statements that are satisfiable if, and only if, $M$ will accept $I$.
The statements do this because they completely describe the exact computation that $M$ would perform starting with string $I$, including an assertion that $M$ would end in an accepting state.
Because of the way the statements are constructed, they can be satisfied if, and only if, $M$ would actually perform a computation that ends by accepting $I$.
If there is no such computation, the clauses are not satisfiable.
So we have this large (but polynomial) family of statements which are satisfiable if, and only if, the machine $M$, which correctly recognizes the language $X$, would accept the particular string $I$.
If we had a satisfying assignment for those statements, that satisfying assignment would exactly describe what $M$ would do in accepting $I$: it would say how $M$ would move its head, and how it would modify the tape over time, and so on, and it would also describe the fact that $M$ would terminate in an accepting state.
So if we could find a satisfying assignment for this large family of statements, we would know that $I$ was in $X$, because we would have a complete description of how the machine $M$, which recognizes $X$, would behave in accepting $I$.
If we could quickly find a satisfying assignment for this large (but polynomial) family of statements, we would be able to quickly decide whether any given $I$ was in $X$, as follows: We would take the string $I$. We would construct the large (but polynomial) family of statements that collectively describe $M$'s computation starting with $I$, including the assertion that $M$ would end in an accepting state. We would quickly check if those statements were satisfiable. If they were, we would know that $M$ would accept $I$; if not then not.
But if we could quickly find satisfying assignments, we could quickly solve every problem $X$ that is in NP, because for every such problem $X$ there is a machine $M$ that recognizes $X$. So an efficient solution to the satisfiability problem would give us an efficient solution to problem $X$ that was in NP. If $X$ is in NP, there is some machine $M$ that recognizes it, and then given any string $I$, we could do just as in the previous paragraph to quickly decide whether $I$ was in $X$.
So an efficient method for finding satisfying assignments can solve efficiently solve any problem $X$ in NP:
Take the machine $M$ that recognizes $X$, construct a set of statements that describe its computation starting from $I$, including the assertion that the computation would end in an accepting state, and then check if those statements can be satisfied. If so, then $I$ is in $X$.
I hope that was some help.
Best Answer
I'm using a second answer to answer your newly added question. You made a little mistake, the cell formula should be the following:
$$\phi_{cell} = \underset{1\leqslant i, j\leqslant n^{k}}{\wedge }\left [ \left ( \underset {s\epsilon C}{\vee} x_{i,j,s} \right ) \wedge \left (\underset{\underset{s\neq t}{s,t\epsilon C}}{\wedge} \left ( \overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right ) \right ) \right ]$$
As you said, the variable $x_{i,j,s}$ represents the symbol s in cell[i,j], so it should be true if and only iff cell[i,j] contains the symbol $s$. Let's analyse the cell formula properly. It exists out of 3 parts:
Combining both points tells us that for each fixed $i$ and $j$ there has to be exactly one symbol $s$ ( NOT MORE AND NOT LESS) so that variable $x_{i,j,s} = 1$. More intuitively it tells us that each cell can only contain exactly one symbol.
Now the only thing left is to analyse is the $\large\underset{1\leqslant i, j\leqslant n^{k}}{\wedge }$ part encapsulating the parts we already analysed. Clearly this part just tells us that the formula has to hold for each cell in the tableau.
I hope this helped.