2

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?

01001101.turing
  • 323

1 Answers1

0

If you're asking what I think you're asking, then consider $EXPTIME$. I think what you're asking is if a model uses $O(f(n))$ resources, then a different model might use $O(g(n))=O(f(n))+p(n)$ for some polynomial $p$ and still be in the same complexity class as the one with $O(f(n))$. If $f(n) = 2^n$ and $g(n)= 2^n+3^n$, would you still consider them in the same complexity class? Yes, even though $p(n) = 3^n$ is not polynomial in this case. Do you see what I'm getting at?

m1cky22
  • 637