This is roughly my guess about P=NP as well, and I suspect the problem will be "solved" when someone figures out how to formalize that progression satisfactorily. Does this sound right, or does anyone know a solid counter-argument?
> Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in nM elementary steps.
> Some of my reasoning is admittedly naïve: It's hard to believe that P ≠ N P and that so many brilliant people have failed to discover why. On the other hand if you imagine a number M that's finite but incredibly large—like say the number 10 3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do nM bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.
> My main point, however, is that I don't believe that the equality P = N P will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M.
That doesn't feel quite the same. My intuition is based on noticing that many instances of NP-complete problems can be solved quickly, and that adding more sophisticated heuristics can put more instances in that category. I'm just guessing that the set of actually-slow instances can be made arbitrarily small if the program is long enough, i.e. has enough special cases for classes of problem that are amenable to faster solutions. It has the same "long enough program" flavor, but I don't think the equality will be quite exact.
