Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 internet speed test! ×
Science

Submission + - Forty Years of P v NP

An anonymous reader writes: In the afternoon of May 4, 1971, 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.

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 was created for logged-in users only, but now has been archived. No new comments can be posted.

Forty Years of P v NP

Comments Filter:

The gent who wakes up and finds himself a success hasn't been asleep.

Working...