Question

Assume that N=NP . Give a polynomial-time algorithm for finding a satisfying assignment for a boolean formula φ, if one exists.

Answer 1

• If P = NP, then there is a deterministic Turing Machine D that solves SAT in polynomial time.

The algorithm can be as follows:

A = “On input φ, where φ is a boolean formula of variables x₁, x₂, x₃, ..., x_k

1. Run D on φ. If φ is not satisfiable, reject. Otherwise

2. For i from 1 to k

3. Replace all the x_is in φ with 1, and simulate D on that.

4. If D accepts, permanently overwrite x_i with 1, otherwise overwrite x_i with 0

Analysis of the algorithm:

This algorithm is definitely in P, since k (the number of variables) is ≤ n.

• Thus the “for loop” and D make it O(k)*O(time of D) => P * P = P (polynomial)

Also the algorithm is accurate. It only gets to the “for loop” if it knows that the formula is satisfiable.