As has been linked on various tech sites, a possible proof of one of the most important outstanding problems in theoretical computer science is currently under peer review. In light of this, it has quickly become the fashion for everyone to pretend that this has significance for the larger tech community.

It’s certainly an “important” result from an academic point of view and some very novel and inspiring work from Vinay Deolalikar (whether holes are found in the proof or not), but I have trouble seeing why anyone not doing research into complexity theory would care about the result.

I’m sure there will be lots of attempts at accessible descriptions of the P versus NP problem written in the next couple of days, with varying levels of success. Instead of dwelling on the particular problem, I’d like to try to explain the significance of this result by extending an analogy I proffered on Twitter.

Suppose a researcher announced a proof that a theoretically perfect gasoline engine would create greater power per unit volume than a theoretically perfect steam engine, including boiler. What consequences would that have?

First you’ve got to dig into what “theoretically perfect” means: in this case I’m imagining an abstraction where the materials to build the engines have no weight or volume, and combustion/expansion operate at 100% efficiency. It’s already a bit obvious that the researcher’s result isn’t necessarily telling us much about which of the two engine types is “better”; if gasoline engines need to be built out of iron but steam engines work fine with aluminum or plastic then steam may outperform gasoline in terms of power to weight ratios.

(The analogy to complexity is that although problems in NP are theoretically “harder” than those in P, the details of solving specific problems in each class can make all the difference. There are plenty of NP-complete problems that can be solved quickly for realistic problem sizes, and plenty of problems in P that are hopelessly intractable in practice. My own research focuses on algorithms to solve a certain type of 2NExpTime problem—i.e. much, much harder than NP—while scaling not much worse than linearly on the types of input data that occur in practice.)

Next, you have to acknowledge the bounds of what the researcher studied: gasoline and steam engines only. Again, if it’s power-to-weight ratio we’re talking about, then things like the weight of fuel matter. If we found some amazing technology for generating heat—and thus steam—using little to no fuel (cold fusion, anyone?), then steam engines would clearly beat gasoline engines until we got into the realm of engines far far bigger than the amount of fuel they need to carry, like drag racers.

(In the few practical situations where P versus NP matters, NP-complete problems are usually just one component among many. In cryptography, for example, the “hard problems” used to protect information are seldom the weak link in the security chain. The fact that a key cannot be directly cracked in polynomial time is neither a necessary nor a sufficient condition to ensure that a cryptographic system is secure.)

But most importantly, you only have to take one small step back to realize that this theoretical result about engine types is telling us (or, as described above, merely hinting at) something we already know: gasoline engines tend to be more powerful than steam engines. The industry figured this out decades ago. If the inverse had been found—that steam engines are theoretically more efficient than gasoline—then the result could have provoked a huge amount of new work on steam engine design. But in fact all we gained was further confidence in our existing assumptions, so work on gasoline engines will continue just as it has done.

(If it had turned out that any problem in NP could be transformed into a problem in P, then there would have been a huge scramble to come up with practical transformations for the major NP-complete problems. But the claimed result is that no such transformations are possible, so there’s no point looking for them. And the truth is, nobody really had been looking: everybody has long assumed that the two classes were unequal. I’ve read quite a few papers containing sentences that include “…and if we assume that P ≠ NP, we can conclude that…”; there’s an acknowledgement in the literature that we’re depending on P ≠ NP, which is not known for sure, but no attempt to explore what the consequences would be if P = NP. The significance of a P ≠ NP proof is that it could remove these caveats from a litany of academic results.)

On the tech community reaction

I’m intrigued by the type of reaction the P ≠ NP proof attempt is getting in the tech community. For the most part the tech sites with a more journalistic approach (strong editorial control; content from staff writers) have stayed away from the story, perhaps waiting for the results of peer review. The more democratic sites that rely on user submissions, such as Digg, Hacker News, and Slashdot, however, are making a big deal of it. Despite the lack of any practical impact, geeks the world over are pretending that this matters to them; suddenly random programmers who took a course or two in computing are reacting as though they were complexity researchers. I don’t recall all the accountants who took a few college classes in mathematics jumping on the Poincaré conjecture bandwagon…