Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question

migrated from Dec 30 '11 at 4:27

This question came from our site for theoretical computer scientists and researchers in related fields.

So I'm new to the TCS stack exchange... I originally posted this question here, but then I deleted and reposted at math stack exchange, as directed in the FAQ. Now a moderator from math stack exchange has moved it back here... – Tony Dec 30 '11 at 3:24
To the person who migrated: This is not research-level, and I think the question fits better math.SE. Tony: You can find the answer at…. – sdcvvc Dec 30 '11 at 3:25
up vote 6 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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