complexity theory: consequences of P vs NP

Question

I have a basic question regarding the ramifications of P vs NP. If P=NP, then SAT would be in P. If I understand the definitions correctly, this would imply that there is a Turing machine which decides SAT in polynomial time. However, does this mean that there would actually be a polynomial-time algorithm for producing a solution of SAT? For instance, what if there were some mysterious polynomial-time computation one could do to a given instance of SAT which would tell you whether or not it was satisfiable, without actually producing a solution (I'm thinking of primality-testing, where for arithmetic reasons it can be easier to verify prime-ness than to actually exhibit a factorization)

Answer 1

The answer is Yes. If P=NP, then not only can you solve the decision problem of SAT, but also you can find the satisfying solution. The reason is that given an instance of SAT, you first ask if it is satisfiable. If so, then consider the first propositional variable. Append this variable and ask if the new system is satisfiable. If so, keep that variable as T, otherwise, you know it must be F. Now move the next variable and so on in turn, asking the two questions of whether the new current system remains satisfiable with that variable being true, and if not, append the negation. This algorithm overall still takes polynomial time, but a higher degree, and leads you to a satisfying solution when one exists.