\documentclass[11pt]{amsart}
\usepackage{amsmath,amssymb,booktabs}
\usepackage[margin=1in]{geometry}
\usepackage{hyperref}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\F}{\mathcal F}
\newcommand{\rk}{\lambda}
\newcommand{\K}{\mathbf K}

\title[Three-machine unit-job scheduling in time $O(L^{276})$]{Three-machine unit-job scheduling\\ in time $O((L+2)^{276})$}
\author{David Niedbala Giraudin}
\address{ORCID: 0009-0009-1526-1178}
\date{3 November 2026}
\begin{document}

\begin{abstract}
OpenAI recently gave a deterministic polynomial-time algorithm for
$P3\mid\mathrm{prec},p_j=1\mid 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})$.
\end{abstract}
\maketitle

\section{Statement}

The problem $P3\mid\mathrm{prec},p_j=1\mid C_{\max}$ is OPEN8 in~\cite{GJ}. We use the notation and numbering of~\cite{OAI}. The input is an explicitly listed directed acyclic
graph on $n$ unit jobs and a deadline $T$; after padding there are $N=3T\le3n$ jobs, and $L\ge n$
is the binary input length. The algorithm of~\cite[\S3]{OAI} is a dynamic program over a family
$\F$ of subsets of $J$ described by Boolean formulas with at most $K=10000$ leaves, the leaves
being: constants; rank thresholds $\rk\le k$, $\rk\ge k$ ($0\le k\le N+1$) in either frame; and
membership in a triple of jobs or in one of its four cones $P,D,\widehat P,\widehat D$, in either
frame. Counting formula instances leaf by leaf gives $|\F|=O(N^{3K})$ and the running time
$O_K(N^{15K+13})$, whence $O((L+2)^{150020})$~\cite[Lemma~2.3 and \S9]{OAI}.

\begin{theorem}\label{thm:main}
The minimum-makespan schedule and the deadline decision of~\cite[Theorem~1.1]{OAI} can be computed
in $O((L+2)^{276})$ steps on a deterministic multitape Turing machine.
\end{theorem}

The algorithm is the one of~\cite{OAI}, run with a smaller family $\F^\ast\subseteq\F$
(Definition~\ref{def:family}) and with fewer reachability passes. Correctness is not re-proved:
soundness of the dynamic program holds for every family~\cite[proof of Proposition~3.1]{OAI}, and
completeness only requires that the node sets and split sets of a bounded-description
hierarchy~\cite[Definition~3.2, Lemma~3.3]{OAI} belong to the family. We check this in
Section~\ref{sec:count}.

\section{Distinct triples and thresholds in the required descriptions}\label{sec:count}

For a formula, let $\tau$ be the number of distinct job triples appearing in its cone or
membership leaves (a triple is counted once, whatever the cones and frames used), and $\theta$ the
number of distinct threshold leaves (a threshold leaf is a frame, a direction and a value).
Sentinel tests are constants and are not counted. An intersection of two rank suffixes
$\{\rk\ge r\}\cap\{\rk\ge r'\}$ in the same frame is the single suffix $\{\rk\ge\max(r,r')\}$,
as noted in~\cite[\S6]{OAI}; we always use this merged form.

\begin{lemma}[only the first entry is trimmed]\label{lem:first}
In every list and every carry of the construction of~\cite[\S\S5--6]{OAI}, every entry other than
the first one carries no outer rank trim.
\end{lemma}
\begin{proof}
The root list $(J)$ and a new switch pair $(G\cap\{\rk\ge h\},D_a)$ \cite[(6.4)]{OAI} have this
property. A carry \cite[(6.1)]{OAI} trims only $K_d$, which becomes its first entry, and discards
$K_1,\dots,K_{d-1}$; the appended injection $D_a\cap(J\setminus P_b)$ \cite[(6.2)]{OAI} is
untrimmed. Pruning only deletes entries; if it deletes the first entry, the entry moving to the
first place is untrimmed. A switch discards the old list entirely. Repeated trims of the first
entry merge into one.
\end{proof}

We bound $(\tau,\theta)$ for the entries. Let $U$ be the parent that produced the node $W$ where a
switch occurs, and use the current frame, in which $U=(a_-,b_-)$ with centre $v_-$
(see~\cite[\S6, before (6.6)]{OAI}). The right boundary of $U$ in the old frame is the triple $a_-$, and its
predecessor cone there is $D_{a_-}$ in the current frame. In the old frame (the tag frame of $W$) we
write $U=(a_U,b_U)$, so that $b_U=a_-$ and $a_U=b_-$ as triples. ``Switch case'' and ``same case''
below refer to the edge $U\to W$, compared with the tag of $U$, as in \cite[Lemma~6.6]{OAI}.

\begin{enumerate}
\item \emph{Root base} $J$: $(0,0)$, plus a trim if first.
\item \emph{Injection} $D_a\cap(J\setminus P_b)$: $(2,0)$, plus a trim if first.
\item \emph{Second switch entry} $D_{a}$: one triple, which is also used in $G$.
\item \emph{The extension $H_-^\ast$ of} \cite[Lemma~6.6]{OAI}. In the switch case it is
$(J\setminus D_{a_U})\cap\{\rk\le r\}$: $(1,1)$. In the same case it is $P_{b_U}$ minus the union of
a carry of the list of $U$, where the possibly complicated first switch entry is replaced by the
flattened pair $D_{a_0}\cup\{\rk\ge k\}$ of \cite[Lemma~6.5]{OAI}. That carry has at most five
entries, at most three of them injections \cite[Lemma~6.4]{OAI}, and at most one trim
(Lemma~\ref{lem:first}); the initial part contributes the root base, or one triple $a_0$ (flattened
pair or second switch entry). Since $P_{b_U}$ is the cone of $a_-$, $H_-^\ast$ uses $a_-$ and at most
$1+6=7$ further triples, and at most one threshold.
\item \emph{First switch entry} $G\cap\{\rk\ge h\}$ with
$G=D_{a_-}\cap(J\setminus\widehat P_a)\cap(J\setminus\widehat P_{v_-})\cap H_-^\ast$
\cite[(6.7)]{OAI}: triples $a_-,a,v_-$ and at most $7$ more, so $\tau\le10$; thresholds: one inside
$H_-^\ast$ and the outer one, so $\theta\le2$.
\end{enumerate}

By \cite[Lemma~6.4 and the remark following it]{OAI} a pruned list, or a carry taken from it, has at most two initial entries
and at most three injections. Hence, using Lemma~\ref{lem:first}:

\begin{lemma}\label{lem:list}
The union of all entries of a pruned list or of a carry uses $\tau\le16$ and $\theta\le2$.
\end{lemma}
\begin{proof}
In a run started by a switch: $10$ triples for the first switch entry, none new for the second,
$2$ for each of at most three injections; thresholds: at most two, both in the first entry.
In the root run: at most $6$ triples and one threshold.
\end{proof}

\begin{proposition}\label{prop:count}
Every global node description of \cite[Lemma~8.1]{OAI} can be written with $\tau\le21$, $\theta\le3$,
and every relative split predicate of \cite[Lemma~8.2]{OAI} with $\tau\le19$, $\theta\le2$; all
these formulas have fewer than $500$ leaves.
\end{proposition}
\begin{proof}
\emph{Same edge.} The description is the union of \cite[(8.4)]{OAI} and \cite[(8.5)]{OAI} with
the cutoff predicate $\widetilde S=P_b\setminus\mathrm{Qual}(\K_{\rm carry})$ \cite[(8.2)]{OAI}.
The new list $\K'$ is the pruned concatenation of $\K_{\rm carry}$ and the injection on $(a,b)$.
The triples are those of $\K_{\rm carry}$ (at most $16$, Lemma~\ref{lem:list}), the parent
boundaries $a,b$, and $a',b',v$: at most $21$. The thresholds are those of $\K_{\rm carry}$, reused
in $\K'$: at most $2$.

\emph{Switch edge.} Here $\K'$ is the pruned switch pair and
$\widetilde S=(J\setminus D_a)\cap\{\rk\le r\}$ \cite[(8.3)]{OAI}. Triples: those of $G$ (at most $10$,
including $a$) and $a',b',b,v$: at most $14$. Thresholds: two in the first switch entry and $r$:
at most $3$.

\emph{Relative splits.} The centre predicate $B_v(H_\ast)$, with
$B_z(H)=P_z\cup(H\setminus\widehat D_z)$ \cite[(4.1)]{OAI} and $H_\ast\in\{P_b,J\setminus D_a\}$,
uses two triples. An internal split $B_v(H_\ast)\cap B_z(\widetilde S)$ \cite[(8.6)]{OAI} uses
$v,z$, the boundary in $H_\ast$ and the triples of $\widetilde S$: at most $3+16=19$ triples and
$2$ thresholds in the same case, and $3$ triples and one threshold in the switch case. The
conversion \cite[(8.7)]{OAI} adds a membership leaf for the triple $z$, already counted.

Merging thresholds only decreases the leaf counts of \cite[Lemma~8.3]{OAI}, which are below $500$.
No other predicate is used: the boundary invariants of \cite[\S7]{OAI} are proved about these
lists and add no description.
\end{proof}

\section{The restricted family and the running time}

\begin{definition}\label{def:family}
Let $\F^\ast$ be the family of subsets of $J$ described by formulas in the atomic language
of~\cite[\S2.3]{OAI} with at most $500$ leaves, at most $21$ distinct triples and at most $3$
distinct threshold leaves.
\end{definition}

By Proposition~\ref{prop:count}, every node set and every relative split set of the
bounded-description hierarchy of \cite[Theorem~3.4]{OAI} belongs to $\F^\ast$, and $J\in\F^\ast$
(formula ``true''). Hence \cite[Lemma~3.3]{OAI} holds with $\F^\ast$ in place of $\F$.

\begin{lemma}\label{lem:size}
$|\F^\ast|\le C\,N^{66}$ for a constant $C$, and $\F^\ast$ can be listed deterministically in
polynomial time.
\end{lemma}
\begin{proof}
Choose a sequence of $21$ triples or blanks ($\le(N^3+1)^{21}$ choices), a sequence of three
threshold leaves or blanks ($\le(4(N+2)+1)^{3}$ choices) and a formula template with at most $500$
leaves over the resulting fixed finite set of atoms (a number of templates independent of $N$).
Since $N\ge3$, $(N^3+1)^{21}(4N+9)^3\le C' N^{63}N^3$. Evaluation and deduplication proceed as in
\cite[Lemma~2.3]{OAI}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
We follow the accounting of \cite[\S9]{OAI} verbatim, with $B=C N^{66}$ in place of $C_KN^{3K}$.
There are at most $B$ sets and at most $S=BN^3$ states per set, and one ordered state-pair test
with its reachability update costs $O(BN^4)$ steps. The only change concerns the number of
passes. Along every transition $|L|$ increases by at least three \cite[proof of
Proposition~3.1]{OAI}, so every path in the state graph of a set has at most $N/3$ edges. After
$p$ passes over all ordered pairs, every state reachable from an initial state by a path of at
most $p$ edges is marked. Hence $\lceil N/3\rceil+1$ passes mark every reachable state, instead of
$S$ passes. For all sets together the cost is
\[
 O\bigl(B\cdot N\cdot S^2\cdot BN^4\bigr)=O(B^4N^{11})=O(N^{4\cdot66+11})=O(N^{275}).
\]
Generating and deduplicating $\F^\ast$ costs $O(B^2N^4)=O(N^{136})$; reachability preprocessing
is polynomial of small degree, and state construction and table initialisation cost at most
$O(B\cdot S\cdot BN^4)=O(N^{3\cdot66+7})$, all far below $N^{275}$.
With $N\le3n\le3L$ (the vertices are explicitly listed, so $L\ge n$), the deadline decision costs $O((L+2)^{275})$, and the $n\le L$ deadline
trials for makespan minimisation give $O((L+2)^{276})$.
\end{proof}

\begin{remark}
Since feasibility is monotone in the deadline, a binary search over $T$ reduces the makespan
computation to $O(\log L)$ deadline trials, giving $O((L+2)^{275}\log(L+2))$.
\end{remark}

\begin{remark}
The improvement does not alter the structural proof of \cite{OAI}: it uses its descriptions as
they stand, and only counts their parameters instead of their leaves. The accounting of the
dynamic program itself is the conservative scan-based one of~\cite[\S9]{OAI}; a finer
implementation of the table lookups would lower the exponent further, which we do not pursue.
\end{remark}

\subsection*{Acknowledgement}
Technical assistance: Claude (Anthropic).

\begin{thebibliography}{9}
\bibitem{GJ} M.~R.~Garey and D.~S.~Johnson, \emph{Computers and Intractability}, Freeman, 1979.
\bibitem{OAI} OpenAI, \emph{A polynomial-time algorithm for three-machine unit-job scheduling},
OpenAI Math Release preprint, September 24, 2026; Lean statement
\texttt{ComparatorChallenges/ThreeMachine.lean} in the same release.
\end{thebibliography}
\end{document}