Explanation of first part of Cook's Theorem

Question

From Introduction to Automata Theory, Languages, and Computation (2nd ed.): pp. 428 - 429

Theorem 10.9: (Cook's Theorem) SAT is NP-complete.

Proof: The first part of the proof is showing that SAT is in NP. This part is easy:

1. Use the nondeterministic ability of an NTM to guess a truth assignment $T$ for the given expression $E$. If the encoded $E$ is of length $n$, then $O(n)$ time suffices on a multitape NTM.

2. Evaluate E for the truth assignment T. If $E(T) = 1$, then accept. Note that this part is deterministic.

The evaluation can be done easily in $O(n^2)$ time on a multitape NTM. Thus, the entire recognition of SAT by the multitape NTM take $O(n^2)$ time.

Why is the time complexity $O(n^2)$? There does not seem to be a justification for this claim.

Answer 1

If you have the CNF formula on one tape and the satisfying assignment on another, you can make a pass through the formula for each variable in the satisfying assignment and check off the clauses satisfied by the value given to that variable. The process can be made to run in quadratic time.

Suppose each literal in the formula is a string of symbols from a fixed alphabet. Suppose a liberal supply of other tape symbols is available to separate literals and clauses. As the TM walks down the formula tape, it tries to match each literal it finds to the one currently scanned on the assignment tape. If it finds a match, it uses another tape symbol to mark the literal as satisfied.

After each literal in the formula tape is processed, the head of the assignment tape is brought back to the beginning of the current assignment literal. The total cost of these rewind operations is proportional to the length of the formula.

After the whole assignment tape has been scanned, one last pass on the formula tape verifies that each clause contains a satisfied literal.

If $n$ is the length of the formula, the length of the assignment tape is $O(n)$, and this gives the overall $O(n^2)$ complexity.