Well, just take n=1...right?
May 4, 2011 9:21 AM Subscribe
In the afternoon of May 4, 1971,
posted by King Bee (19 comments total)
6 users marked this as a favorite
in the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete
and Tautology is NP-hard.
40 years ago today, Cook presented his paper on the problem we know today as the "P v. NP
" problem, or the hypothesis "P = NP".
From the wikipedia link: "Suppose that solutions to a problem can be verified quickly. Then, can the solutions themselves also be computed quickly?" If you can answer this question, you'll get a million dollars from the Clay Institute
and a ton of accolades.
Some interesting problems which are not known to be in P or NP-complete are the integer factorization problem
. Even still, if it turns out that P=NP, then we're going to have to retire RSA encryption
, and the fatal flaws
in the proposed "proof"