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?

Improve this question
$\endgroup$
5
  • $\begingroup$ > If it satisfies ϕ, return it. What do you do when it doesn't satisfy? $\endgroup$
    – Curtis F
    Sep 2, 2018 at 23:18
  • 2
    $\begingroup$ You have to use self-reducibility of SAT. $\endgroup$
    – Yuval Filmus
    Sep 3, 2018 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, 2018 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, 2018 at 11:09
  • $\begingroup$ Which textbook and where is the answer?! $\endgroup$
    – alan23273850
    Mar 25 at 13:18

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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