Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.