Forty Years of P=NP?

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."

P=PN

[jjohn]

15 years of developing software and I still don't know what P vs. NP means.

Sad, sad old hacker.

Wow Slashdot has gone downhill...

[DNS-and-BIND]

I looked in to this discussion just because I wanted to see what the hardcore science/math nerds were saying, and instead I get a dozen posts asking, "What the hell is P=NP, LOL." Time was, you could look into math threads on Slashdot and see graduate students talking shop. Even if I didn't understand half of what they said, it was still enlightening.

Re:P = NP?

[hey!]

I've been in this business since the 1980s. When I started, there were proportionately a lot more math geeks in software than there are today, but by the early 90s there wouldn't have been enough math geeks in all the world to do the work that needed to be done. The people who came into the business had the attitude that complexity and computation theory were just a lot of ivory tower rubbish.

There was a certain validity to this attitude. There was ton of work to be done, but almost all of it amounted to assembling endless variations of the same old kinds applications but in new contexts. It was like snapping together different Lego projects. The mathematically difficult work had already been done for the people engaged in that work, and so their intellectual focus shifted to issues of craft and project management, which were by no means trivial things. Some of us kept algorithm books handy for that odd job where the library routines didn't quite do, but we didn't really need much math. We just needed a rough grasp of O notation and the ability to translate pseudocode into C. Most software guys didn't even go that far. They didn't have *any* math books or references on their shelves, just big, fat tutorial books on vendor provided solutions or architectural philosophy.

Then came the Internet.

A lot of Internet related software falls into the Lego Architecture class, but given a world of data that are interconnected, there's more need than ever for people who can create *new* algorithms that can squeeze gems of value out of that mountain of data quicker than the Universe will perish from heat death. Companies like Google or Facebook or LinkedIn can't just slap a Java front end onto an Oracle database. They have to create new ways to structure and process volumes of data magnitudes beyond anything that existed in the early 1990s.

Fundamental (in the sense of "foundational" rather than "beginner's") CS is once again very practical knowledge to have.