# 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.