1
$\begingroup$

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

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.