Definition of Complexity Classes

260 Views Asked by At

The definitions I've seen for 'complexity class' all seem to be variations on "the set of problems that can be solved by an abstract machine of type $M$ using $O(f(n))$ of resource $R$, where $n$ is the size of the input" (Wikipedia). Papadimitriou points out in his text on the subject that reasonable models of computation only pin down resource usage to within a polynomial (e.g. a $\Theta(n)$ algorithm under one model of computation becomes $\Theta(n^2)$ or $\Theta(n^5)$ under others). Why not restrict the definition of `complexity class' to reflect this?

I have something like the following in mind: "the set of problems that can be solved by an abstract machine of type $M$ using $O(f(n))$ of resource $R$ for some $f \in \Gamma$ where $\Gamma$ is a polynomially-closed set of functions and $n$ is the size of the input". Perhaps I'm wrong, but this seems to both preserve all of the complexity classes I've seen (admittedly, not a large number) and ensure that complexity classes are independent of the particular model of computation in use. Thoughts?