NP’s more challenging problems often have momentous practical applications. For these problems, an exhaustive brute-force search for a solution would likely go on for an impractically long time—geologic time—before producing an answer. If a brute-force search algorithm is the best algorithm possible, then P does not equal NP.
And among the cognoscenti, that’s apparently the consensus, which some liken more to religious belief: P ≠ NP. Most allow only a sliver of hope that the opposite will prove true. “I’d give it a 2 to 3% chance that P equals NP,” Aaronson says. “Those are the betting odds that I’d take.”
The result published in July presented a proof of exactly that long shot. But it was only the latest in a long tradition of proofs that don’t pass muster. Within a day of publication, in a turn of events worthy of Monty Python, the paper was removed from the online journal; then it seemed to reappear briefly before disappearing permanently. It was the most recent version of a paper that the author had posted more than 60 times to the arXiv preprint server over the last decade. The journal’s editor in chief explained on Twitter that the result had been rejected, but in a case of human error, the paper’s disposition had somehow changed from “reject” to “accept” and the proof had found its way to publication.
3. In early August, when I met Steve Cook at his office on campus, he’d neither seen nor heard of that latest P vs. NP proof snafu. Now 81, he’d only recently retired, since his memory was failing. “That’s why we have James here,” he said—his son James, 36, also a computer scientist, had joined us for my visit. Steve was in the midst of clearing out his office. A giant recycling bin stood in the middle of the room, filling up with old yellowing issues of the Journal of Symbolic Logic, a stack of super-fat Toronto telephone books waiting nearby.
Over the years, Cook has seen many proofs purporting to solve the P vs. NP problem. In 2000, after the Clay Mathematics Institute named it one of the seven unsolved “Millennium Problems” (each worth a $1 million prize), he was inundated with messages from people who thought they’d triumphed. All the results were wrong, if not plainly bogus. About half claimed to have proved that P equals NP; the other half went in the opposite direction. Not too long ago, one person claimed to have proved both.
Cook, in his 1971 paper, conjectured that P does not equal NP (he phrased it using different terminology common at the time). He’s since invested a significant if indeterminate amount of time working to establish that that’s the case. “I don’t have a good memory of toiling away,” he says, but his colleagues recall that whenever they went into the department on the weekend, Steve was there in his office.
Unless he’s racing sailboats, Cook is not one to rush; he likes to give