Monday, November 01, 2010

By Any Other Name Would Be Just As Hard

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.


  1. The main problem with terms like "NP-hard" and "NP-complete" is most definitely the "NP" part. The modifiers "hard" and "complete" work quite well. They are relatively intuitive, and they can be applied to a wide range of complexity classes (as opposed to, say "herculean" or "arduous").

    Meanwhile, it's quite annoying that the best way to explain the fields most well known problem, P vs. NP, involves delicately sidestepping the "N" word. A more "PC" alternative (i.e. polynomial time checkable) would make the situation far less uncomfortable.

  2. By changing the names I believe we would introduce more confusion.

    However, if I was able to select names then I would go for this:

    "NP-complete" belong to NP and can be thought as containing all the other problems. Thus, I would use the term
    NP-descriptive, since they can be used to describe any problem in the class.

    For "NP-hard" I would use NP-supreme, due to the resemblance to the supremum.

    I believe the original terms are much more intuitive than my ideas!

  3. I agree with EERac that "nondeterministic polynomial" is not a good name for public consumption.


  4. Can you give some examples of "giant questions" in other fields and their simple names?

  5. I agree that NP is a confusing name, but it is mostly because "nondeterminism" is confusing and hard to explain. On the other hand, the alternative definition which is more popular these days is much more intuitive: VP, verifiable in polynomial time. We could have had two definitions NP and VP and then prove in the lectures/textbooks that VP = NP, and then use VP in place of NP from that point, and in a few years we could have droped using NP, but unfortunately Valiant has already used this one.

  6. Giant Questions:

    The Riemann hyothesis.
    If solved this would tell us much about
    primes so it seems big. Though it does not
    dominate Number Theory the way that
    P vs NP dominates complexity.

    The Goldbach Conjecture. This is a motivating problem, probably also NOT quite what you mean.

    You ask a good question- do other fields have problems (and what are there names) that drive them the way
    P vs NP drives us?

  7. GASARCH asks: "Do other fields have problems (and what are their names) that drive them the way P vs NP drives us?"

    The clear answer is "yes," and to add spice to the question, if the problem arose in the 20th century, then it is a remarkably safe bet that John von Neumann played a role in formulating it.

    Consider the range of problems that von Neumann played a key role in conceiving/defining: optimal strategies for winning games, controlling dynamical systems, and searching sets ... JvN ... consistency and decidability of formal systems ... JvN ... computational modeling of systems and enterprises ... JvN ... quantum measurement processes ... JvN ... microscopy at atomic resolution ... JvN ... DNA as a molecular string with a finite number of letters ... JvN.

    As for the still-unanswered "Giant Question" of a whether our small-ish planet Earth can support its large-ish number of people in freedom, security, and dignity ... well ... that is the still-unsolved question that JvN was working on when he passed away (at the too-young age of 54).

    Perhaps it would be a good thing if we kept working on that last JvN problem, as subsequent history has shown us that it is going to be an exceedingly tough one.

  8. "Riemann Hypothesis" and "Goldbach Conjecture" sound no more friendly to the "commoner"

  9. Here is your theory cafe:

  10. "practically unsolvable" would have been a good term :-)

  11. It's also interesting to know that, in addition to the $1 million from the Clay Institute, Knuth promises 1 live turkey for a proof that P=NP. However, a proof of P \neq NP would only qualify for the money, not the turkey.

  12. Is "hard" really an accurate way of describing complete problems for a class? Every complete problem sits somewhere in that class: circuit-sat is solvable in time bounded by a specific polynomial, say of degree d. But there are plenty of problems in P that are much "harder" than circuit-sat: problems that can't be solved faster than say 2d or 2^d or 2^2^d. And they may well not be P-complete*. So then in what sense is circuit-sat "harder" than them?

    Really, completeness is a statement about expressivity, or encodability. It says that a specific problem is sufficiently expressive to encode any problem from a comparable resource class.

    *Q: Is there any theorem known about the distribution of, say. P-complete problems? Like, is it possible for there to be a P-complete problem solvable in linear-time?

  13. Of course, I mean circuit-value, NOT circuit-sat. Circuit-sat being solvable in polynomial time would quite an interesting result...