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.

Mike Trick’s post on the status of P=NP is required reading.  He writes about a new review paper on the status of P=NP (by Lance Fortnow at Northwestern) and its corresponding New York Times article.  I had not heard about either.  There have been a few recent developments on the P=NP front (check out the blog Godel’s Lost Letter and P=NP for updates).  I have trouble keeping track of all of the news and had always felt like a review article was needed.  I am thrilled that one now exists, along with the newspaper article to explain the concept more clearly to non-experts.  I will be using both in some of my classes.  For more info, please check out Mike Trick’s blog post.

I recently saw my first silent movie: The Passion of Joan of Arc. Much to my surprise, I loved it. I can’t wait to see another (I’ve got my eye on Nosferatu). I loved just about everything about the Passion of Joan of Arc and I didn’t miss the lack of dialogue. The movie translated just a few of the lines that were “spoken” during the movie. Much of the dialogue was left for the viewer to “hear” by reading lips and body language. The acting and camera work conveyed the emotion of Joan of Arc’s short life and trial, and it packed an incredible punch (Roger Ebert explains why this movie is a masterpiece much better than I can).

After seeing the film, I reflected on movies and technology. Movies are not just a product of technology but are also shaped by technology. Each time that movie technology changes, the movie experience fundamentally changes. Because special effects and dialogue are so easy to put in movies these days, there is too much CGI and talking to have an emotionally moving moviegoing experience most of the time. Most movies fail to convey what they really should be conveying, and as a result are flat and uninspiring (There are plenty of exceptions, and a quick glance at my Netflix history includes Tully, Gone Baby Gone, Lars and the Real Girl, Bella, and Juno).

The same can be said about operations research. We work in a technology-driven field, where we rely on software to do much of our work for us. Sometimes we rely on software too much and on good modeling too little. A IIE blog entry writes about blindly using software as a quick fix. When computing power wasn’t very powerful, making a tight, efficient formulation was necessary for finding optimal solutions. I hope we haven’t lost some of the art of OR.

This past week, I have been working on a research problem that is formulated as an integer program. I was curious to see what the optimal solutions look like, so I popped it into CPLEX. After letting CPLEX churn away on it for more than 72 hours, I felt a little guilty that I didn’t spend more time to make an elegant and efficient IP formulation. There may be a great theoretical research problem to work on, but alas, I know that it was just laziness. Just because computing is cheap and easy doesn’t mean that I shouldn’t pay attention to theoretical aspects. Although to be fair, I thought there was a good chance that CPLEX would very quickly find an optimal solution, which offered little incentive to consider various formulations. We don’t want to lose sight of important theoretical contributions just because it is easier to focus on computational challenges in OR. With journals like Mathematics of Operations Research that publish theoretical contributions to OR and journals like INFORMS Journal on Computing that publish truly innovative computing research, I am not worried for our field. But I will sit down and try to make my a masterpiece rather than let CPLEX churn on endlessly (Eventually, mbuilding had a power outage, so I never found the optimal solution with CPLEX. I wrote some code that takes just a couple of hours to run. It’s not the most elegant algorithm, but an improvement).