Comment by NotOscarWilde
1 day ago
As a TCS/scheduling person, this one is definitely of lesser importance than UGC, but it has been an open problem since the book of Garey and Johnson in 1979:
A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling [1]
Since some people talk about small numbers that pop up in integer multiplication results, here a completely different number appears:
Theorem 1.1. Let an explicitly listed finite directed acyclic graph specify the precedence constraints on n >= 1 nonpreemptive unit-length jobs on three identical machines. There is a uniform deterministic algorithm that constructs a feasible schedule of minimum makespan. Given also an integer deadline 1 <= T <= n, it decides feasibility exactly and returns a schedule whenever the answer is affirmative. Both tasks can be performed in O((L + 2)^150020) steps on a deterministic multitape Turing machine, where L is the total binary input length.
That is some crazy exponent -- plus an interestingly old computational model to boot; not something that is natural to most of us. I have no capacity to check its correctness today, but I hope it is true purely for the exponent.
[1]: https://github.com/openai/math/blob/main/preprints/A-polynom...
The largest I've seen [1] is an exponent of 10^12, which I suppose still counts as polynomial time.
I'm sure all of these super small or large constants will improve over time, but it's still amusing. It is entertaining to see the exponents directly rather than have them hidden as n^c or epsilon or O(1).
[1]: https://github.com/openai/math/blob/main/preprints/Determini...
That's why I grimace when I see pop-sci descriptions of P as "all problems that can be solved efficiently".
To be fair, there is a pretty strong correlation between a problem being in BPP and being efficiently solvable in practice.
There are some exceptions of course (graph isomorphism was solved in practice when the best theoretical algorithms were still exponential) but in general once people find a n^100000 algorithm it soon turns into a n^3 algorithm with reasonable coefficients.
1 reply →
It's efficient, but somewhat slow..
The runtime looks very weird. The +2 can and should be dropped. This reduces my confidence that the bound is tight. Who knows how the model came up with that expression.
Is it mostly an artifact of the proof or does the algorithm actually need anything close to it?