We're almost done with the proof that satisfiability is NP complete.
But before making the final arguments,
I want to remind you what we're trying to do.
Consider some language in NP, and suppose that someone wants to be able to
determine whether strings are in this language.
The Cook-Levin theorem argues that because L is in NP,
there's a non-deterministic turn machine that decides it.
And it uses this fact to create a function computable in polynomial time
that takes in any input string X, and
outputs a boolean formula that is satisfiable.
If and only if, the string X is in the language L.
That way, any polynomial algorithm for deciding satisfiability
will be able to decide every language in NP in polynomial time.
Only two questions remain.
Is the reduction correct, and is it polynomial in the size of the input?
Let's consider correctness first.
If X is in the language, then clearly the output formula is satisfiable.
We can just use the truth assignment that corresponds to an accepting
computation of the non-deterministic turning machine that accepts X,
that will satisfy the formula F.
That much is certainly true.
How about the other direction?
Does the formula being satisfiable imply that X is in the language?
Take some satisfying assignment for F.
As we've argued, the corresponding tableax is well-defined.
Only one of the state variables can be true at any time, etc.
The Tableax also starts in the initial configuration.
Every transition is valid, and
the configuration sequence ends in an accepting state.
That's all that's needed for
a non-deterministic turn machine to accept.
So yes, this direction is true as well.
Now we have to argue that the reduction is polynomial.
First, I claim that the running time is polynomial in the output formula length.
There just isn't much calculation to be done besides
iterating over the combination of steps, head positions, states and tate symbols,
and printing out the associated terms of the formula.
Second, I claim that the output formula is polynomial in the input length.
Let's go back and count.
These clauses, pertaining to the states,
require order p of n times log n string length.
The number of states to the machine is a constant in this context.
The p factor comes from the number of steps of the machine.
The four i here.
The log in factor comes from the fact that we have to distinguish the literals
from one another.
This requires log in bits.
In fact, in all these calculations, that's where the log factor comes from.
For the head position, we have order p of nq to log n string length.
One factor p comes from the number of steps, and
we have two coming from all pairs of head positions.
They're order p squared combinations of steps and squares.
So this family of clauses requires order p squared log n length as well.
The size of the alphabet is a constant in this context.
As for the constraints pertaining to the initial configuration,
this require order p log n string length.
The dominant factor being the constraints
about the contents of the tape.
And the constraint that the computation be accepting requires only log n string
length, since it just has to write out this single literal one clause here.
The transition clauses might seem like they would require
a high order polynomial of symbols.
But remember that the size of the non-deterministic turning machine
is a constant in this context.
Therefore, the fact that we might have to write out clauses for
all pairs of state and tape symbols, doesn't affect asymptotic analysis.
Only the range of the indices i and j depend on the size of the input string.
So we end up with order p squared log n string length for
all these transition clauses.
Summing the length of all those clauses up together,
we have a sum of polynomials, which is of course a polynomial.
So yes, the overall reduction is a polynomial and Cooks theorem is proved.