>
One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial complexities are given such special status. It's just taken for granted that polynomials are the class you care about... with no explanation as to why.
The reason is that if we take something more fine-grained than polynomial, whether the runtime is in this class or not can strongly depend on the machine model (e.g. Turing machine, register machine (counter machine, pointer machine, random-access stored-program machine), etc.). On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for.
Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea.
The reason is that if we take something more fine-grained than polynomial, whether the runtime is in this class or not can strongly depend on the machine model (e.g. Turing machine, register machine (counter machine, pointer machine, random-access stored-program machine), etc.). On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for.
Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea.