3 ms·
SAT is the boolean satisfiability problem, a simple NP-complete problem often used to prove the other problems are NP-complete. An instance of SAT is a boolean
by alextp 17y ago
SAT is the boolean satisfiability problem, a simple NP-complete problem often used to prove the other problems are NP-complete. An instance of SAT is a boolean formula, and the answer to it is yes if and only if the formula can be true for some assignment of variables. 3SAT is the same problem, only with the formula in a conjunctive normal form and each clause having exactly three variables.
Also, it seems the poster is really just trying to get attention. Complexity theorists do know all that and have spent a lot of time trying to see which postulated consequences of P?=NP are necessary and which are not.
(If I were to argue it is an ill-posed question, I'd go more in the direction of CO-NP (which is the set of problems for which "NO" answers have short certificates), and why this really strong emphasys on "yes" certificates for NP problems)
Doron Zeilberger's take on that ( http://www.math.rutgers.edu/~zeilberg/Opinion98.html http://www.math.rutgers.edu/~zeilberg/Opinion98.html ) is a lot more interesting.
And, also, the "easy" equals "polynomial time" is (a) a good heuristic, if you assume computational power increases exponentially (hence, a problem will be solvable in the foreseeable future if all it needs is polynomially more processing power for larger instances); (b) it is an easy to study class, since it is composable; (c) not the only thing complexity theorists argue about (ie, P=NP means practical bounds for some problems and collapses a lot of classes that are not trivially seen to be equal, like AM and MA)
- anatoly 17y agoI think your evaluation of the post may have been somewhat rushed. - The poster is a notable complexity theorist and is not "just trying to get attention". - Doron Zeilberger's "a lot more interesting" take is completely subsumed in Richard Lipton's blogpost, in that it mentions other possibilities beyond the basic "what if it's polynomial with a really huge exponent" scenario. - Assuming computational power to increase exponentially indefinitely is completely ridiculous, and without the "indefinitely" part this assumption no longer works to justify "easy = P". - It is trivial to say that if P=NP, then AM=MA, because both AM and MA are in the polynomial hierarchy, and if P=NP, the hierarchy collapses completely. - The most important point to be taken away from the blogpost is not just that "easy = P" is an assumption that's been held on too unreflectively and may not turn out to be true. It's that studying what this assumption means, how it could break down, and why it hasn't, by and large, broken down so far, may get us closer to understanding P ?= NP.
- alextp 17y agoYou have a point. My closeted complexity theorist persona thinks it would be a lot more interesting to study the special cases of P (not just LOG, but seeing how O(n) and O(n²) or "NO(n)" problems behave) instead of the most general cases.