<p>It's equivalent (under Turing reduction) to deciding whether the language of <em>any</em> given TM is empty.  That is, it is co-RE-complete.  This can be shown using a standard padding argument.</p>
<p>Here are the details.
Let <span class="math-container">$E_P$</span> denote the problem in question (deciding whether <span class="math-container">$L(M)=\emptyset$</span> for a given TM <span class="math-container">$M$</span>, with the promise that <span class="math-container">$M$</span> runs in polynomial time).</p>
<p><strong>Lemma 1.</strong> <em><span class="math-container">$E_P$</span> is co-RE-complete.</em></p>
<p><em>Proof.</em>
Let <span class="math-container">$E_{TM} = \{\langle M \rangle : L(M) = \emptyset\}$</span> denote the problem of deciding whether the language of a given TM is empty.
Note that <span class="math-container">$E_{TM}$</span> is co-RE-complete. (The complement of <span class="math-container">$E_{TM}$</span> is RE-hard by Rice's theorem, and in RE by a standard dovetailing argument.)</p>
<p>Clearly <span class="math-container">$E_P$</span> reduces to <span class="math-container">$E_{TM}$</span> (the reduction, given <span class="math-container">$\langle M\rangle$</span>, can simply output <span class="math-container">$\langle M \rangle$</span>).</p>
<p>To finish, we show the converse, that <span class="math-container">$E_{TM}$</span> reduces to <span class="math-container">$E_P$</span>.
Given (the encoding of) an arbitrary TM <span class="math-container">$M$</span>, the reduction will output the encoding of a TM <span class="math-container">$M'$</span> such that <span class="math-container">$M'$</span> is guaranteed to run in polytime, and <span class="math-container">$L(M') = \emptyset$</span> iff <span class="math-container">$L(M)=\emptyset$</span>.</p>
<p>The idea is that <span class="math-container">$L(M')$</span> will be the set of pairs <span class="math-container">$(w, 1^i)$</span> such that <span class="math-container">$M(w)$</span> accepts within <span class="math-container">$i$</span> steps.  Given an input <span class="math-container">$(w, 1^i)$</span>, the machine <span class="math-container">$M'$</span> simply simulates <span class="math-container">$M$</span> on input <span class="math-container">$w$</span> for <span class="math-container">$i$</span> steps, then accepts if <span class="math-container">$M$</span> does (within <span class="math-container">$i$</span> steps).  The simulation is done efficiently so that the time it takes is polynomial in the input size, <span class="math-container">$|w| + i$</span>.  (This is not hard.)  By construction, <span class="math-container">$L(M')$</span> is as desired, so <span class="math-container">$L(M')$</span> is empty iff <span class="math-container">$L(M)$</span> is empty.</p>
<p>Finally, given the encoding of <span class="math-container">$M$</span>, the encoding of <span class="math-container">$M'$</span> is computable. <span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2024-02-01T13:49:53.267Z
2024-02-01T15:36:26.600Z
2024-02-01T15:36:26.600Z
Neal Young
<p>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?</p>

<cc.complexity-theory><turing-machines>
Complexity of determining whether the language of an P machine is empty
user1868607
# Complexity of determining whether the language of an P machine is empty

(Asked by: username_0 on 2024-02-01)

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?

**Tags:** cc.complexity-theory, turing-machines

---

## 1 answers

### Answer by username_1 on 2024-02-01. Score: 6 | Accepted answer

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$


---

