There is an interesting part of Lance Fortnow’s book The Golden Ticket: P, NP, and the Search for the Impossible about how we got the name “NP-complete:”
What should people call those hardest problems in NP? Cook called them by a technical name “deg({DNF tautologies}),” and Karp used the term “(polynomial) complete.” But those names didn’t feel right.
Donald Knuth took up this cause. in 1974 Knuth received the Turing Award for his research and his monumental three-volume series, The Art of COmputer Programming. For the fourth volume, Knuth, realizing the incredible importance of the P versus NP problem, wanted to settle the naming issue for the hardest sets in NP. In 1973, Knuth ran a poll via postal mail. He famously doesn’t use email today, but back in 1973 neither did anyone else.
Knuth suggested “Herculean,” formidable,” and “arduous,” none of which fared well in the poll. Knuth got many write-in suggestions, some straightforward, like “intractable,” “obstinate,” and others a bit more tongue-in-cheek, like “hard-boiled” (in honor of Cook) and “hard-ass” (“hard as satisfiability”). [Laura: Read Knuth’s post in ACM SIGACT News]
The winning write-in vote was for “NP-complete,” which was proposed by several people at Bell Labs in New Jersey after considerable discussion among the researchers there. The word “complete” comes from mathematical logic, where a set of facts is complete if it can explain all the true statements in some logical system. Analogously, “NP-complete” means these problems in NP powerful enough that they can be used to solve any other problems in NP.
Knuth was not entirely happy with this choice but was willing to live with it. He truly wanted a single English word that captured the intuitive meaning of hard search problems, a term for the masses. In a 1974 wrap-up of his survey, Knuth wrote, “NP-complete actually smacks of being a little too technical for a mass audience, but it’s not so bad as to be unusable.”
“NP-complete” quickly became the standard terminology.
The emphasis/underlining is mine. Sorry for the PG-13 title. On a related note, if you haven’t read Richard Karp’s seminal paper “Complexity of Computer Computations,” I recommend it!
R.M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, eds.), Plenum Press, 1972, pp. 85–103.
Punk Rock Operations Research 
February 17th, 2014 at 11:59 am
I find this statement to be very prescient: “NP-complete actually smacks of being a little too technical for a mass audience, but it’s not so bad as to be unusable.”
All the CS people I meet know what it means. A majority of OR people know what it means. A decent fraction of mathematicians know what it means. Outside of those fields, at least in my experience, the term is gibberish. And it’s a really frustrating term to explain to people, because the intuitive and easy explanation (“NP-complete means that it requires an exponentially-increasing amount of computation time”) is completely wrong.