4 ms·
I feel like your claim is begging the question. It's certainly not true in principle that most problems in P have a small exponent. There is no shortage of gra
by Maxatar 2y ago
I feel like your claim is begging the question.
It's certainly not true in principle that most problems in P have a small exponent. There is no shortage of graph related algorithms in P that have absolutely absurd exponents, like on the order of 10^100. It is true that practical decision problems that are in P have small exponents but that's exactly the point being made, namely that problems in P with large exponents are not practical and hence don't get much attention.
- Laakeri 2y agoWhat are examples of natural graph related problems in P with absurd exponents? I think the reason they don't get attention is not that the algorithms are not practical, but that the problems are not natural. Really, the only examples of such problems I can think of are something like "Finding a clique of size 222222 is in P because we can try all possibilities in n^222222 time".