But it makes no sense. P doesn't mean fast, it means polynomial. A runtime of O(n + a) is polynomial (and just O(n)!), but with a big enough "a" (e.g. 2^99999

But it makes no sense. P doesn't mean fast, it means polynomial. A runtime of O(n + a) is polynomial (and just O(n)!), but with a big enough "a" (e.g. 2^999999999999999999999999999999999) it's likely large enough to be practically non-commutable. I.e. there are "practically non-commutable" polynomial algorithm. So the idea "there is not proof because we should have found it else wise" is deeply flawed.