Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.