Three machines, polynomial?

0:00Scheduling with precedence

Some jobs must wait for others: a precedence graph says that job u must finish before job v starts. Every job takes one unit of time, and there are a few identical machines. How short can the schedule be? With two machines, Fujii, Kasami and Ninomiya, and then Coffman and Graham, found optimal schedules in polynomial time; Coffman and Graham’s rule labels the jobs and always runs the highest-labelled jobs that are ready. On three machines the same rule can fail. In our check, breaking ties by job number, it was optimal on all 1,500 random two-machine instances, but on three machines it lost on 4 of 20,000 random graphs, each time rescued by a different tie-break. In this 12-job example, found by a longer search, it needs five steps however ties are broken, because it starts the wrong job first, while four steps suffice. When the number of machines is part of the input, Ullman showed the problem is NP-complete. For exactly three machines, the question appears among the open problems in Garey and Johnson’s 1979 book, and it has remained a central open question in scheduling. Special cases fell: Garey, Johnson, Tarjan and Yannakakis handled opposing forests in linear time, and Dolev and Warmuth graphs of bounded height. Approximation schemes followed, for any fixed number of machines: from Levey and Rothvoss, then Garg in quasipolynomial time, Li in even less, and a simpler one from Das and Wiese. In 2025, Nederlof, Swennenhuis and Węgrzycki gave an exact algorithm in time 2^(O(√(n log n))) for three machines. But there was no polynomial-time algorithm, and no hardness proof.

1:44The claim

Result 124 is a single OpenAI preprint, 22 pages, dated September 24. It claims a uniform deterministic algorithm that, for any explicitly listed precedence graph on unit-length jobs and three identical machines, constructs a schedule of minimum length, and, given a deadline, decides exactly whether it can be met, returning a schedule if so. The running time is O((L + 2)^150020), on a multitape Turing machine, where L is the length of the input. That is a polynomial, so, if the proof is right, it settles the open problem in favour of polynomial time. The exponent is enormous, and the paper makes no practical claim. By our count, for a 10-job chain in the encoding of the Lean statement, (L + 2)^150020 has about 350,000 digits. The model is exactly the classic one, with no release dates and no communication delays. OpenAI published a Lean formalization whose main theorem states that a single multitape Turing machine answers both the optimization and the deadline questions correctly within a constant times that bound, in 53 files and about 18,600 lines with its imports, not counting Mathlib. We have not run the Lean check ourselves.

3:09How it works

First, pad the instance with isolated jobs, so that every time slot holds exactly three. Remove some slots from a feasible schedule, and each gap between them can be rescheduled on its own, since reordering its jobs never changes whether they come before or after any job outside. So the algorithm works through sets of jobs, smallest first, accepting a set only when it can piece together a schedule for it. A set is accepted if a chain of triples of jobs, each able to run in one time step, cuts it so that the jobs before the first triple, between neighbouring triples, and after the last are all smaller accepted sets. Run over every subset, this is exponential. In our check, done that way, it agreed with brute force on all 130 small deadline questions where the jobs fit in the available slots. The point is which sets to consider. The algorithm uses only sets described by a Boolean formula with at most 10,000 leaves, built from three kinds of test: precedence to or from a triple of jobs, membership in that triple, and rank thresholds in a fixed linear extension or its reverse. There are only polynomially many such sets, roughly the number of jobs to the power 30,000. A deliberately generous count of the search’s steps on a Turing machine then gives the exponent: 15 × 10,000, plus a little. The structural theorem says that every feasible schedule has a recursive decomposition in which every gap, at every depth, is one of these sets, in fact with fewer than 500 leaves. To find such a decomposition, the proof fixes a priority order that extends precedence, and calls an initial segment of it low and the rest high. A slot separates this cutoff when every high job scheduled earlier is a prerequisite of some job in that slot, and every low job scheduled later must wait for one of them. In a lexicographically least schedule, promoting jobs one at a time from high to low moves a separator forward, and each pair of consecutive selected slots separates a common cutoff. This builds on the decompositions of Dolev and Warmuth, and of Nederlof, Swennenhuis and Węgrzycki. The danger is that a gap’s description inherits conditions from all its ancestors. The proof treats the two sides of a center slot alike, reversing time and precedence on one side, and keeps only a short list of sets closed under taking successors. Here the three machines matter: each surviving new entry needs its own job in the boundary triple, so at most three new entries survive, and with at most two set up at the last change of direction, at most 5 entries remain. A global boundary condition excludes distant jobs, an exchange condition keeps it valid after later reorderings, and at each change of direction the inherited history is flattened into a short formula. It matches the history only inside the parent interval, so precedence tests confine its use there, and every gap still gets a description valid on all jobs, not just inside the gap.

6:16Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the full theorem, a multitape Turing machine with the stated time bound; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, scheduling unit jobs with precedence constraints on three machines is solvable in polynomial time, settling the question from Garey and Johnson’s list in favour of polynomial time, more than 45 years later. The argument uses three machines directly, makes no claim about four or more, and gives no practical algorithm.