1
$\begingroup$

I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$.

If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$.

I'm not sure how to proceed from here. Any hints?

$\endgroup$
2
  • 1
    $\begingroup$ Hint: if there are only a constant number of words, say $m$, not in $A$, how many symbols of the input do you need to read to decide if it is in $A$ or not? $\endgroup$
    – dkaeae
    Nov 27, 2018 at 8:58
  • 1
    $\begingroup$ What's the complexity of deciding finite languages? $\endgroup$
    – Raphael
    Nov 27, 2018 at 11:47

1 Answer 1

1
$\begingroup$

Your observation that co-finite languages are regular and hence in linear time is absolutely correct. Unfortunately, it's not enough, since there are definitely regular languages that require linear, and not constant, time (e.g., even checking if your input matches $0^*$ requires you to look at the whole input, unless $\Sigma=\{0\}$).

There are only finitely many strings not in a co-finite language. So, how much input do you need to read before you know whether the input is one of those?

$\endgroup$

Your Answer

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

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