cs.DS — Data Structures and Algorithms
Three-machine unit-job scheduling in time O((L+2)^276)
OpenAI recently gave a deterministic polynomial-time algorithm for P3|prec,p_j=1|C_max (problem OPEN8 of Garey and Johnson), with running time O((L+2)^150020) on a multitape Turing machine, L being the input length; the same exponent appears in the accompanying Lean statement. The exponent comes from enumerating all Boolean formulas with at most 10000 leaves, each leaf choosing its own triple of jobs. We show that every description actually used by the structural proof involves at most 21 distinct job triples and at most 3 distinct rank thresholds. Restricting the enumerated family accordingly, and using the length bound on accepting paths already proved there to limit the number of reachability passes, the same algorithm runs in time O((L+2)^276).