Follow Slashdot blog updates by subscribing to our blog RSS feed


Forgot your password?

Slashdot videos: Now with more Slashdot!

  • View

  • Discuss

  • Share

We've improved Slashdot's video section; now you can view our video interviews, product close-ups and site visits with all the usual Slashdot options to comment, share, etc. No more walled garden! It's a work in progress -- we hope you'll check it out (Learn more about the recent updates).

Math Science

Forty Years of P=NP? 222

Posted by CmdrTaco
from the turns-out-they-both-equal-seven dept.
An anonymous reader writes "In the afternoon of May 4, 1971, at 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. 'The theorems suggest that Tautology is a good candidate for an interesting set not in [P] and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.' And thus Cook formulated what was soon to be called the P versus NP problem. The rest is history. Here's the 1971 STOC Program (there were 143 attendees) and what that sacred ground looks like today."
This discussion has been archived. No new comments can be posted.

Forty Years of P=NP?

Comments Filter:
  • Re:P=PN (Score:2, Insightful)

    by war4peace (1628283) on Wednesday May 04, 2011 @09:45AM (#36024078)
    Make that two of us. And guess what, I don't even care :)
  • Re:P = NP? (Score:5, Insightful)

    by vlm (69642) on Wednesday May 04, 2011 @09:53AM (#36024174)

    Can anyone explain what all the fuss is about ?

    Its strongly related to the "CS" vs "IT" division amongst "computer people". Its hard to find a topic that more strongly shows the separation.

    The "IT" guys simply don't care (look at many of the posts in this article) but for the "CS" guys its proof would be pretty close to the ultimate "super bowl win" or "moon landing" or "date with a girl" moment.

"Nature is very un-American. Nature never hurries." -- William George Jordan