Reasons I deem more likely: 1. Selection effect: if it’s unfeasible you don’t work on it/don’t hear about it, in my personal experience n^3 is already slow 2. If in n^k k is high, probably you have some representation where k is a parameter and so you say it’s exponential in k, not that it’s polinomial
1: Not true, I hear about exponential time algorithms! People work on all sorts of problems only known to have exponential time algorithms.
2: Yes, but the reason k only shows up as something we would interpret as a parameter and not as a result of the computational complexity of an algorithm invented for a natural problem is perhaps because of my original point—we can only invent the algorithm if the problem has structure that suggests the algorithm, in which case the algorithm is collapsible and k can be separated out as an additional input for a simpler algorithm.
Reasons I deem more likely:
1. Selection effect: if it’s unfeasible you don’t work on it/don’t hear about it, in my personal experience n^3 is already slow
2. If in n^k k is high, probably you have some representation where k is a parameter and so you say it’s exponential in k, not that it’s polinomial
1: Not true, I hear about exponential time algorithms! People work on all sorts of problems only known to have exponential time algorithms.
2: Yes, but the reason k only shows up as something we would interpret as a parameter and not as a result of the computational complexity of an algorithm invented for a natural problem is perhaps because of my original point—we can only invent the algorithm if the problem has structure that suggests the algorithm, in which case the algorithm is collapsible and k can be separated out as an additional input for a simpler algorithm.