Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] By Any Other Name Would Be Just As Hard

Expand Messages
  • Lance
    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
    Message 1 of 1 , Nov 1, 2010
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.