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 an idea time. And his former students remember a distinct lack of swagger. The computer scientist Anna Lubiw, at the University of Waterloo, says that when he taught Cook’s theorem—part of that pioneering paper—he never referred to it as such and never even gave any hints that he was the person who proved it. Maria Klawe, a mathematician and computer scientist and the president of Harvey Mudd College, says she would regularly correct Cook when he lost his way teaching proofs that he knew inside out: “He’d get stuck and say, ‘Okay. Tell me how the proof goes.’” Cook was also famously modest in grant applications and reports pertaining to his research—he’d confess: “Honestly, I have made little progress …”
https://www.technologyreview.com/2021/10/27/1037123/p-np-theoretical-computer-science/
