Read the definition of the SAT problem on page 249 of the bo

Read the definition of the SAT problem on page 249 of the book. In short, SAT is a generalization of 2-SAT or 3-SAT, but now there is no limit on the number of literals per clause. The input size of an instance of SAT is the total number of literals in the input formula F. Call that m, and let n be the number of different variables that appear in F. Is SAT in NP? Justify your answer. SAT can be solved by building a truth-table with 2^n different assignments of T/F to the n variables; and then checking each assignment to see if it satisfies formula F. Explain why that approach is not a polynomial-time algorithm to solve SAT. That is, explain why that approach takes exponential time in worst case, as a function of input size m. Note that m n.

Solution

There is a multitape NTM that can decide if a Boolean formula of length n is satisfiable.

The NTM takes O(n²) time along any path.

Use nondeterminism to guess a truth assignment on a second tape.

Replace all variables by guessed truth values.

Evaluate the formula for this assignment.