Three-machine unit-job scheduling with precedence constraints (Garey-Johnson OPEN8): is P3|prec,p_j=1|Cmax in P?
Given a directed acyclic graph on unit-length jobs and a deadline , can the jobs be scheduled on identical machines, at most per time slot, so that every precedence has strictly before and all jobs finish by ? For this is polynomial (Fujii-Kasami-Ninomiya 1969, Coffman-Graham 1972); with part of the input it is NP-complete (Ullman 1975). The fixed case , , is listed as open problem OPEN8 in Garey and Johnson's book; the best exact algorithm known ran in time (Nederlof-Swennenhuis-Wegrzycki). Is three-machine unit-job scheduling with precedence constraints solvable in polynomial time, or is it NP-complete?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Scheduling theory; computational complexity
- Posed by
- Michael R. Garey and David S. Johnson, Computers and Intractability (1979), Appendix A13, OPEN8
- Year posed
- 1979
- Years open
- 47y
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 45 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: a uniform deterministic algorithm constructs a minimum-makespan schedule for unit-length jobs with arbitrary precedence constraints on three identical machines, and decides feasibility for a deadline exactly, in Turing machine steps. The method decomposes schedules into gaps whose job sets have bounded-size global Boolean descriptions and searches them by dynamic programming. The exponent is astronomically large and no practical claim is made. It does not settle fixed machines, which remains open.
What the AI did
The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author.
Verification
No independent mathematician has checked this yet. Checked here: Theorem 1.1 of the manuscript was read against the problem as stated there (explicit DAG, unit jobs, three identical machines, no release dates); it claims a deterministic algorithm producing a minimum-makespan schedule and deciding feasibility for a given deadline in multitape Turing machine steps. The proof was not refereed. The challenge is not in the formalization catalogue (lean/formalization.yaml); it is found through lean/docs/124.md, and its solution module OAI.Computability.Scheduling.Main exists at the pinned commit. The statement ComparatorChallenges/ThreeMachine.lean was read here: it encodes instances and answers as bit strings and asserts one fixed multitape machine and constant such that, for every nonempty acyclic instance and every deadline option with , the machine halts within steps with a correct output (an optimal schedule, or a feasible schedule or a correct 'infeasible'). This states the headline claim, polynomiality included. Not rebuilt here.