3 ms·
I re-implemented a quasi-polynomial algorithm. Experimentally, it shows exponential behaviour. Back-of-the-envelope calculation shows this behaviour can continu
by rrobukef 6y ago
I re-implemented a quasi-polynomial algorithm. Experimentally, it shows exponential behaviour. Back-of-the-envelope calculation shows this behaviour can continue until the input size is >>10^21 before the asymptotic bound asserts itself.
(For comparison, input size 30 is unfeasible)
- Ragib_Zaman 6y agoWhich algorithm?
- rrobukef 6y agoParys' quasi-polynomial algorithm for solving parity games, https://arxiv.org/pdf/1904.12446.pdf https://arxiv.org/pdf/1904.12446.pdf Note, another implementation doesn't have this behaviour for the family of inputs I use. It's an implementation detail that has no effect on correctness. Thus for the other implementation another family should exist.