MathOverflow is a question and answer site for professional mathematicians. 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

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.