Gerhard Woeginger

A generous record

Gerhard Woeginger died on 1 April 2022. His colleagues remembered a great scientist, a dear friend, and a scholar with a rare gift for finding the heart of an argument. Their memorial records, among far larger things, that he set up and maintained the P versus NP page.

The page was a generous act. For twenty years it gave every claimed proof the same steady treatment: a numbered entry, a factual note, and a link to the work where one existed. This Register continues that work with respect. It keeps his notes as a distinct historical layer, makes no judgment of any author, and shows where later review has and has not happened.

Read the Journal of Scheduling memorial by Lenstra, Rendl, Spieksma and Uetz.

Visit the preserved frozen page.

The world the list froze in

On 5 November 2015, BBC Radio 4's In Our Time gave the problem a full episode. Melvyn Bragg's guests were Colva Roney-Dougal, Timothy Gowers and Leslie Ann Goldberg. The register's final entry was ten months away. The episode is a portrait of the world this list froze in.

The panel made the problem honest for anyone. A travelling salesman must visit every city once and come home by the shortest route. With five cities it feels easy. With two hundred, the possible routes blow past anything a computer could ever try. Or seat 150 wedding guests along one long table when several of them loathe each other. Checking a finished plan is one slow walk round the table. Finding a plan from scratch is the hard part. That is the whole problem in one sentence: some answers are easy to check and, as far as anyone knows, brutally hard to find. Every dossier in this register is a claim about that line.

The line is thinner than it looks. Pairing people into compatible twos is genuinely easy; a clever algorithm has existed since the 1960s. Ask for compatible threes instead and the problem becomes as hard as anything in NP. One small change, and the floor gives way.

The panel also explained why a proof stays out of reach. Mathematicians have shown, roughly speaking, that any proof that P and NP differ would have to be a strange proof, and strange carries a formal meaning here: whole families of natural attack are ruled out in advance. They cited the 2012 poll in which about 80% of those polled backed P not equal to NP, and recalled Donald Knuth's standing offer: he thinks P = NP so unlikely that the first person to prove it gets a live turkey along with the million dollars. The claimants in Woeginger's own list leaned the other way. Of the 116 historical dossiers, 61 argue P = NP.

Then, live on air, history arrived early. The panel let slip word of “a little rumor going around, as of yesterday or so”: a famous mathematician would give a talk in Chicago the following Tuesday, on graph isomorphism. History knows it as László Babai's quasi-polynomial graph isomorphism result, one of the decade's biggest advances in complexity theory. Radio caught it while it was still a rumour, days old and not yet checked.

Ten months later, in September 2016, dossier 116 landed and the page fell quiet. The field kept moving. The list did not.

Listen to the episode at the BBC.

The keeper's craft

It is worth saying plainly what made the page good, because the craft is easy to miss.

• One keeper. The page spoke with a single voice and held a single standard for twenty years.
• Plain HTML. No database, no framework, no accounts. A page anyone could read, save and cite, on any machine. That plainness is why a byte-exact copy still exists to preserve.
• Fairness by record. Each entry stated what the author claimed, in neutral terms. Claims, never people. No entry mocked its author, and none ever will here.
• No verdicts he had not earned. Where a refutation existed, he pointed to it. Where none existed, he recorded nothing, and the silence was honest. That honesty is why 100 of his 116 entries stand unadjudicated today, a fact about the field's attention rather than the claims' merit.

The silence after 2016 taught the other lesson. The page was only as alive as its keeper. When his attention moved on, the list froze; after his death it could never restart. Every mirror of it is a photograph now. Nothing in the craft failed. The single point of failure was a person, as it always is.

That lesson is built into this Register. His frozen page is preserved byte-exact as the historical layer it now is. The watchers that check the sources publish their own heartbeats, and every page states when it was generated and when its sources were last checked. The record is a hashed, append-only ledger, so the register can outlive any one keeper without losing its honesty. People still make every judgment; the machine only keeps the pulse. A register is only as alive as its keeper, so this one's heartbeat is public.