Follow Slashdot blog updates by subscribing to our blog RSS feed

 



Forgot your password?
typodupeerror
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. ×
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:

No amount of careful planning will ever replace dumb luck.

Working...