Question

Show that if $\mathit{P}\mathbf{=}\mathit{N}\mathit{P}$, a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. (Note: The algorithm you are asked to provide computes a function; but $\mathit{N}\mathit{P}$contains languages, not functions. The $\mathit{P}\mathbf{=}\mathit{N}\mathit{P}$assumption implies that $\mathit{S}\mathit{A}\mathit{T}$is in $\mathit{P}$, so testing satisfiability is solvable in polynomial time. But the assumption doesn’t say how this test is done, and the test may not reveal satisfying assignments. You must show that you can find them anyway. Hint: Use the satisfiability tester repeatedly to find the assignment bit-by-bit.)

Short answer

Choose $x_1=1$if ${\varphi }_0$is satisfiable; otherwise, choose $x_1=1$if ${\varphi }_1$ is satisfiable. In a satisfied assignment, this gives the value of $x_1$. Make the replacement permanent, and in the same way, find a value for $x_2$in a satisfying assignment. Continue unitl all the variables are substituted.

Step-by-step solution

Step-1: SAT

The (Boolean Satisfiability Challenge) is the problem of finding whether or not a given boolean formula has an interpretation that satisfies it. It examines whether the variables in a given boolean formula can be consistently replaced with the values $TRUE$or $FALSE$, resulting in the formula evaluating to $TRUE$. The formula is said to be satisfiable if this is the case. If no such assignment occurs, the formula's function is$FALSE$ for all conceivable variable assignments, thus the formula is unsatisfactory.

Step-2: Explanation

There exists a polynomial time technique for deciding $SATifP=NP$. Substitute $x_1=0and{x}_1=1$ in to create a satisfactory assignment for a satisfiable formula $\varphi$ , and then test the satisfiability of the two resulting formulas ${\varphi }_0$ and ${\varphi }_1$. Because $\varphi$ is satisfiable, at least one of them must be satisfiable. Choose $x_1=1$if role="math" localid="1663243564370" ${\varphi }_0$ is satisfiable; otherwise, choose $x_1=1$if ${\varphi }_1$ is satisfiable. In a satisfied assignment, this gives the value of $x_1$. Make the replacement permanent, and in the same way, find a value for $x_2$ in a satisfying assignment. Continue until substituted all of the variables.