2
$\begingroup$

I was reading a paper and I came across the term $L\notin i.o.Dtime(2^{n^c}/n^c)$. What is the meaning of this?

$\endgroup$
3
$\begingroup$

$L\in DTIME\left(2^{n^c}/n^c\right)$ if there exists a machine $M$ running in time $O\left(2^{n^c}/n^c\right)$ which correctly decides membership to $L$ for an infinite number of input lengths, i.e. for every $k\in\mathbb{N}$ there exists $n\ge k$ such that $\forall x\in\{0,1\}^n : M(x)=\mathbb{1}_{x\in L}$. You can think of it as having a non trivial special case where we can decide membership to $L$ (where by non trivial I mean an infinite set of inputs, not just very short ones).

$\endgroup$
3
  • $\begingroup$ Then what is the difference between normal classes and infinitely often. Why it mentions infinitely often explicitly? Any normal class is generalized for any length input.. $\endgroup$ Dec 6 '20 at 6:32
  • $\begingroup$ I didn't say all input lengths, consider the language $L=\big\{\langle M\rangle | L(M)=\Sigma^* \lor |\langle M \rangle| \text{ is odd}\big\}$ is infinitely often linear, since I can trivially handle odd length inputs, even though $L$ itself is undecidable. $\endgroup$
    – Ariel
    Dec 6 '20 at 6:40
  • $\begingroup$ Okay got it...Thanks $\endgroup$ Dec 6 '20 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.