So, OK then, why not just try to quantify the amount of “explicit knowledge” that the algorithm has about the solution, and show that exponentially many steps are needed before there can be an appreciable amount of such knowledge? Well, to see the difficulty of that strategy, consider any even slightly-interesting polynomial-time algorithm—e.g., for greatest common divisor, or maximum matching, or finding eigenvalues of a matrix. Such algorithms work by doing complicated transformations of the input. If you were just staring at a memory dump, it might not be obvious to you that the algorithm was gaining *any knowledge at all* about the solution, until everything suddenly came together at the very last step. Or rather: it wouldn’t be obvious to you *unless* you understood how the algorithm worked, at a higher, “semantic” level.

(And in fact, almost every amateur “proof” of P≠NP I’ve ever seen could be rejected for the simple reason that nothing it said was specific to NP-complete problems. I.e., if the argument worked to show any algorithm needed exponential time to “gather enough information” to solve a 3SAT instance, then an exactly parallel argument would *also* have worked for 2SAT. Yet for 2SAT, we know a linear-time algorithm.)

Worse yet, Razborov and Rudich’s natural proofs barrier shows that, in a certain sense, any approach to proving P≠NP that follows the algorithm step-by-step, and explicitly calculates how “complicated” is the information that the algorithm has produced so far (showing that exponentially many steps are needed before it’s “complicated enough”), is inherently doomed to failure. For, if such an approach worked, we could also use it to efficiently distinguish random functions from pseudorandom functions, which is one of the very problems we were trying to prove was hard.

This shouldn’t be interpreted to mean that proving P≠NP is *impossible*: in fact, diagonalization (the thing Turing used to show the unsolvability of the halting problem) is already a technique that evades the barrier pointed out by Razborov and Rudich. (Unfortunately, diagonalization falls prey to a different barrier, called *relativization*—but this comment is getting too long.) What it means, rather, is that if you’re trying to prove some problem is not in P, then you’d better zero in on something highly *specific* about that problem, rather than just trying to argue that the solution is “complicated,” and no algorithm could generate anything so “complicated” after a polynomial number of steps.

(Which is something that one could’ve realized, and that careful thinkers *did* realize, even before Razborov and Rudich—but the latter made the point sharper and more formal.)

lewikee’s question actually got me thinking – doesn’t the core reason that we think we can’t solve NP-hard problems in P time that there is just not enough information gained at each step? My intuition is kind of that, for a problem with an exponential number of possible solutions, each of the P steps has to kind of provide an exponential jump in the amount of information we have about the solution.

Can you provide any info on how this has been explored from an information theoretic perspective?

]]>Then there’s the Time Hierarchy Theorem, which lets us make lots of interesting unconditional statements, such as:

- There is no polynomial-time algorithm to decide whether White has the win from a given position, in an nxn generalization of chess.

There is no polynomial-time algorithm to decide whether a statement about integers, involving quantifiers, variables, constants, and addition (but no multiplication), is true or false. (Even though this problem is decidable, in a stack-of-exponentials running time.)

Here are a few other examples of things that we know:

- There are no polynomial-size circuits of AND and OR gates (and no NOT gates) to solve the CLIQUE or MATCHING problems. (Even though there

There is no polynomial-size, constant-depth, unbounded-fanin circuit of AND, OR, and NOT gates to compute the parity or majority of an n-bit string.

There is no algorithm that solves SAT simultaneously in sublinear space and O(n^{1.7}) time.

Once again, all of these things *have been proved*, despite the unlimited number of new mathematical concepts and algorithmic techniques that might be invented in the future—much as Fermat’s Last Theorem has been proved, despite the unlimited number of ideas that might be invented in the future to search for counterexamples to it. (Since the time of Euclid, you might say, the entire appeal of math has been its ability to encompass an infinity of cases in a single, finite argument.)

Obviously, P≠NP is vastly harder than any of the examples I mentioned—if it weren’t, then it would’ve been solved already. But I think the existence of these known lower bounds (and dozens more that I didn’t mention) should certainly cause one to question the belief that P≠NP must be fundamentally unprovable.

]]>