Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a language $L$, you can talk about the complexity of a Turing machine $M$ which decides $L$. Can you talk about the time complexity of the language $L$ itself, i.e. say $L$ has complexity $f(n)$ iff

  1. There exists a Turing machine deciding $L$ in time $O(f(n))$
  2. All Turing machines deciding $L$ have complexity $\Omega(f(n))$

Under what conditions does a language have a (time or space) complexity in this way? Does it matter if you relax $O()$ and $\Omega()$ to ignore sublogarithmic, or logarithmic, or polynomial factors?

I am aware of some languages that do not have complexity, i.e. there is no single Turing machine which attains the lower bound on running time. For example, in the decision procedure for WS1S requires time at least $2 \uparrow \uparrow O(n)$, yet for any machine $M$ deciding WS1S, there is another such machine $M'$ which is exponentially faster than $M$.

share|improve this question
add comment

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.