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?

  • $\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$ 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$ 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$ Sep 3, 2018 at 11:09
  • $\begingroup$ Which textbook and where is the answer?! $\endgroup$ Mar 25, 2023 at 13:18

1 Answer 1


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.


Your Answer

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

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