Some connections between mathematical logic and complexity theory
Richard A. DeMillo, Richard J. Lipton · 1979
However difficult the fundamental problems of theoretical computer science may seem, there is very little to suggest that they are anything more than knotty combinatorial problems. So, when we look for reasons for our inability to resolve P = NP and related questions, we most likely find them dealing with a lack of understanding of particular computational problems and their lower bounds. This is the sense of Hopcroft's prediction: “...within the next five years, nobody will prove that any of these problems takes more than let's say n2 time. I think that's a reasonably safe conjecture and it also illustrates how little we know about lower bounds.” [MT]. Hopcroft's guess is uncanny in its accuracy—after six years and considerable effort by many researchers, his conjecture remains unchallenged.