In 1973 Donald Knuth searched for a name for the hardest problems in NP. Steve Cook didn't give a name in his paper and Karp called them P-complete. Knuth suggested three names "Herculean", "Formidable" and "Arduous". He sent out a ballot to people in the theory community and also allowed write-in votes.

The results he put in a SIGACT News

Article, a fascinating and hilarious read. Of course Knuth's suggestions didn't fly and he got many quite inventive counter-proposals. My favorite: Hard-Ass Problems (Hard As satisfiability).

The winning solution came from a group at Bell Labs (likely including one of their new hires David Johnson), which you readers should all know as NP-hard and NP-complete. These names did have the advantage that it could generalize to other notions of hardness (like PSPACE-complete).

Knuth muses at the end

NP-hard problems hits lots of people, and that's why I began searching for a special term. In other words, I don't consider it a major goal to invent descriptive terminology for every conceivably interesting question of the type considered here; the major goal is to have a good term to use for the masses, in the one case which experience shows is almost omnipresent. To say NP-hard actually smacks of being a little too technical for a mass audience, but it's not so bad as to be unusable.

The importance of the P versus NP problems has reached well beyond the theory community despite its name but I wish Knuth had been more successful in finding a descriptive term. P, NP, NP-hard and NP-complete are technical names that tend to isolate us and confuse others.

--

Posted By Lance to Computational Complexity at 11/01/2010 09:11:00 AM