# P=NP giving a deterministic algorithm for SAT

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?

• > If it satisfies ϕ, return it. What do you do when it doesn't satisfy? – Curtis F Sep 2 '18 at 23:18
• You have to use self-reducibility of SAT. – Yuval Filmus Sep 3 '18 at 4:43
• @Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness. – David Richerby Sep 3 '18 at 11:07
• @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. – David Richerby Sep 3 '18 at 11:09

$\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.