[Math] If P = NP, then 3-SAT can be solved in P

computabilitycomputational complexitycomputer science

Prove that if $P = NP$, then there is an algorithm that can find a boolean assignment for a 3-SAT problem in P time if it exists.

$P = NP$ only says that we can decide whether a 3-SAT problem is satisfiable but it doesn't say anything about how to find a satisfying boolean expression.

Does any one know how to tackle this problem?

Best Answer

Take your formula and check if it is satisfiable. If so, conjoin $x_1$ to your formula, where $x_1$ is your first variable, and check if it is still satisfiable. If so, then there is an assignment where $x_1$ is true; otherwise, there is one where $x_1$ is false.

Conjoin $x_1$ or $\neg x_1$ and repeat for all of the other variables.

Related Question