1
$\begingroup$

I'm trying to prove the following problem:

Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:

INPUT: A boolean formula $\phi$.
OUTPUT: A satisfying assignment of $\phi$ if $\phi$ is satisfiable. If $\phi$ is unsatisfiable, return $false$.

My proof:

If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $\phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $\phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.

Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?

$\endgroup$
  • $\begingroup$ > If it satisfies ϕ, return it. What do you do when it doesn't satisfy? $\endgroup$ – Curtis F Sep 2 '18 at 23:18
  • 2
    $\begingroup$ You have to use self-reducibility of SAT. $\endgroup$ – Yuval Filmus Sep 3 '18 at 4:43
  • $\begingroup$ @Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness. $\endgroup$ – David Richerby Sep 3 '18 at 11:07
  • $\begingroup$ @CurtisF The asker is proposing an algorithm that uses nondeterminism, and then trying to use P=NP to conclude that there is an equivalent deterministic one. $\endgroup$ – David Richerby Sep 3 '18 at 11:09
5
$\begingroup$

I like the way you think, but there's a gap in your attempt.

$\mathrm{P}$ and $\mathrm{NP}$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $\mathrm{NP}$, so the assumption that $\mathrm{P}=\mathrm{NP}$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.