3
$\begingroup$

Suppose you are given a deterministic Turing machine and you are guaranteed it runs in polynomial time. What's the computational complexity of determining whether the language accepted by the machine is empty?

$\endgroup$
0

1 Answer 1

6
$\begingroup$

It's equivalent (under Turing reduction) to deciding whether the language of any given TM is empty. That is, it is co-RE-complete. This can be shown using a standard padding argument.

Here are the details. Let $E_P$ denote the problem in question (deciding whether $L(M)=\emptyset$ for a given TM $M$, with the promise that $M$ runs in polynomial time).

Lemma 1. $E_P$ is co-RE-complete.

Proof. Let $E_{TM} = \{\langle M \rangle : L(M) = \emptyset\}$ denote the problem of deciding whether the language of a given TM is empty. Note that $E_{TM}$ is co-RE-complete. (The complement of $E_{TM}$ is RE-hard by Rice's theorem, and in RE by a standard dovetailing argument.)

Clearly $E_P$ reduces to $E_{TM}$ (the reduction, given $\langle M\rangle$, can simply output $\langle M \rangle$).

To finish, we show the converse, that $E_{TM}$ reduces to $E_P$. Given (the encoding of) an arbitrary TM $M$, the reduction will output the encoding of a TM $M'$ such that $M'$ is guaranteed to run in polytime, and $L(M') = \emptyset$ iff $L(M)=\emptyset$.

The idea is that $L(M')$ will be the set of pairs $(w, 1^i)$ such that $M(w)$ accepts within $i$ steps. Given an input $(w, 1^i)$, the machine $M'$ simply simulates $M$ on input $w$ for $i$ steps, then accepts if $M$ does (within $i$ steps). The simulation is done efficiently so that the time it takes is polynomial in the input size, $|w| + i$. (This is not hard.) By construction, $L(M')$ is as desired, so $L(M')$ is empty iff $L(M)$ is empty.

Finally, given the encoding of $M$, the encoding of $M'$ is computable. $~~~~\Box$

$\endgroup$

Your Answer

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

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