Skip to main content
2 of 2
added 159 characters in body
usul
  • 4.5k
  • 27
  • 30

A polynomial-time algorithm for SAT (satisfiability), the problem of whether a boolean logical formula has a setting of its variables that makes it true.

(It's not quite in the letter of the question because we do not know that it does not exist.)

Primarily, we show that problems are NP-hard by reducing SAT (or another NP-hard problem) to those problems in polynomial time. The argument is thus that, if we have a polytime algorithm for those problems, then this constructs a polytime algorithm for SAT. Since we do not believe this mythical creature exists, we do not think those problems can be solved efficiently. (not sure if all mathematicians are already aware of this or whether the summary is useful.)

If we had this polynomial-time algorithm for SAT, then we could prove theorems quickly and automatically, we could break cryptosystems, we could improve massively in all sorts of scheduling, routing, resource allocation, and other optimization problems -- in short, "useful" would be an understatement.

(Let me add -- what's really "useful" is the converse: if this object does not exist, then we know that these sorts of tasks cannot be accomplished.)

usul
  • 4.5k
  • 27
  • 30