8
$\begingroup$

In my theory computation class, I was told that early computer pioneers didn't realize that some problems are intrinsically hard—what we now call NP-hard problems. Instead, it took a while to realize that some problems could be solved with better programming, and others... well, they couldn't.

For example, early sort programs were relatively slow, because they were limited by both available memory and algorithmic issues. I read the sort algorithm for the Univac and it's a merge-sort algorithm that uses multiple tape drives to sort more data than will fit in the computer's memory. As memories got larger, merge sort and heapsort became dominant. Then Hoare invented Quicksort in 1959, and people were really surprised, both because of its elegance and its efficiency.

Other problems didn't get a fantastic speedup—for example, scheduling. We now know that many of these are NP-complete, and possibly even harder than NP-hard. (PSPACE problems might be harder than NP problems, but then again, they might not be.)

My understanding is that NP-hard predates NP-complete, and I recently found this lovely article by Johnson, "A Brief History of NP-Completeness 1954-2012", which traces the history of the concept.

What I would like to know is when people working in the field did realize that some problems were intrinsically hard and that they weren't going to get dramatically faster solutions with simply more clever programming (absent a significant mathematical breakthrough). After all, linear programming was invented in World War II, and so with that, my guess is that many problems that seemed hard also seemed solvable. So, when did people discover that some problems are not?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ I do not think the divide between programmers and theoreticians existed in the early days. Von Neumann was the designer and the programmer of EDVAC. Knuth's Art of Computer Programming, that brought theory to practice, started coming out in 1963. A discussion of NP-hard problems was planned for volume 4 as early as 1973. Your own link names Karp's "influential paper" of 1972 as the threshold from which the idea gains wide circulation. $\endgroup$
    – Conifold
    Mar 13, 2020 at 4:16
  • $\begingroup$ What do you define as a "programmer" ? A large part of quality programming involves being aware that you can't improve the code without doing flow-charts, mathematical analysis (e.g. for speed of convergence), and so on. $\endgroup$
    – Carl Witthoft
    Mar 13, 2020 at 12:14
  • $\begingroup$ My uncle's senior thesis was on the 'backpack problem' as an NP-complete problem. He graduated in 1962 and had a long career with IBM (not surprisingly). $\endgroup$
    – Jon Custer
    Mar 13, 2020 at 13:12
  • 1
    $\begingroup$ @JonCuster, I don't think that your uncle wrote a thesis about NP-complete problems in 1962, as the term wasn't coined until 1972. The NP-complete/NP-hard terminology was settled in 1974 $\endgroup$
    – vy32
    Mar 13, 2020 at 22:59
  • 4
    $\begingroup$ Again, your link answers the new phrasing as well. Godel and Nash realized it in mid-50s, although it only appeared in print a decade later, due to Cobham and Edmonds, albeit addressed to mathematical audiences. If "the field" means computer programming then Cook, Levin and Karp addressed those in 1971-72, and after that it was pretty much "realized". I am just not sure what we can add that Johnson did not already cover. $\endgroup$
    – Conifold
    Mar 13, 2020 at 23:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.