Three-machine unit-job scheduling in time O((L+2)^276)
Source: hexagonmath.org/abs/2611.00060v1
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00060
curl -X POST /api/v1/records/hexagon/2611.00060/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00060/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'