7
$\begingroup$

Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial time. Note that there can be machines that run needlessly long but still decide a language in $P$. By Rice's theorem, we know that

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) \in P \mbox{ } \}$ is undecidable. Is it known whether:

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }M \in P \mbox{ } \}$ is also undecidable?

$\endgroup$
  • 1
    $\begingroup$ By Rice's theorem, you also have that this language is undecidable (non trivial property). $\endgroup$ – Tpecatte Sep 8 '13 at 17:59
  • 2
    $\begingroup$ Timot: No, Rice's theorem does not apply to the second language, because whether $M \in P$ is not a property of $L(M)$. OP: You can use the answer given in cstheory.stackexchange.com/questions/5004 $\endgroup$ – sdcvvc Sep 8 '13 at 18:22
  • $\begingroup$ Why can't you use the same diagonalization proof as Rice's theorem ? $\endgroup$ – Tpecatte Sep 8 '13 at 19:04
  • $\begingroup$ Timot: I think the proof cannot be reused since a non-P machine might decide a P language. The underlying idea is similar but IMO not the same. $\endgroup$ – sdcvvc Sep 8 '13 at 20:47
6
$\begingroup$

Here is a paraphrase of the proof in the cstheory answer. We reduce from the halting problem. Suppose that we are given a machine $M$, and we are to decide whether $M$ halts on the empty input. We construct a new machine $M'$ accepting a single input $x$, which operates as follows:

  1. Let $n = |x|$.
  2. $M'$ runs $M$ for $n$ steps.
  3. If $M$ halted within $n$ steps then $M'$ runs a dummy loop taking exponential time $\Omega(2^n)$. Otherwise, $M'$ just halts.

Since Turing machines can be simulated with only polynomial overhead, if $M$ doesn't halt then $M'$ runs in polynomial time. If $M$ halts, then $M'$ takes exponential time. Hence $M$ halts iff $M'$ is not polynomial time.


More generally, this shows that even if we know that $M$ runs in time at most $f(n)$ for some superpolynomial time-constructible $f$, then we cannot decide whether $M$ runs in polynomial time.

$\endgroup$
  • $\begingroup$ I have a doubt. If M run in halts in $O(2^n)$ then $M^{'}$ runs in polynomial time although $M^{'}$ halts. Am I missing something ? $\endgroup$ – sashas Feb 22 '16 at 12:02
  • $\begingroup$ @sasha I don't follow your question. $\endgroup$ – Yuval Filmus Feb 22 '16 at 15:36
  • $\begingroup$ I am having trouble seeing if the reduction above also works for $L= \{ <M> \; | \; \text{M runs in P(n) steps where P(n) is some fixed polynomial} \}$. $\endgroup$ – sashas Feb 22 '16 at 16:07
  • $\begingroup$ @sasha I see no particular problem. $\endgroup$ – Yuval Filmus Feb 22 '16 at 16:09
  • $\begingroup$ If $M$ halts on empty input in $2^n$, $M^{'}$ runs in polynomial time. Am I missing something ? $\endgroup$ – sashas Feb 22 '16 at 16:22
2
$\begingroup$

The way your second language is written is not exactly well formed in regards to normal standards. $P$ is a set of languages and not a set of machines. Based on what you said in the rest of your question, I assume that you are trying to make the distinction between machines that run in at most polynomial time and those which happen solve a problem in $P$. Perhaps this would be a better way to write it as:

$A=\left \{ \left \langle M \right \rangle | (\exists k \forall x) M(x) \text{ halts in } O \left ( |x|^{k}\right ) \text{ time} \right \}$

$O$ can be replaced with $\Theta$ if you want to exclude weaker machines such as log-time TMs.

Note that: $A\subset\{\langle M \rangle|L(M) \in P \}$

As observed by sdcvvc, Rice's theorem does not immediately apply and suffice here since the "non-trivial" property used has to be a property of $L(M)$. A time bound on a machine is not a property of the language, but rather is a property of that machine.

An answer for a predetermined $k$ was discussed the cstheory question question referred to in the comments. The choice of that constant was the key to proving the undecidability. In our language, we include any $k\in\mathbb{N}$ and therefore do not have a maximal $k$ to work with.

I have not had time to spend to sufficiently investigate, but I imagine that it would not be unreasonable to extend their results to any $k>2$ via straight forward induction.

A recent paper written by David Gajser, who was motivated by that the cstheory post, answers a more generalized version of this question:

Let $HALT_{T(n)} = \{ \langle M\rangle|\forall x M(x) \text{ halts in at most } T(n=|x|) \text{ time}\}$

For single tape Turing Machines: $HALT_{T(n)}$ is undecidable if $T(n)= \Omega(nlog(n))$

For multiple tape Turing Machines: $HALT_{T(n)}$ is decidable iff $T(n) \leq k+1$ for some $k\in \mathbb{N}$

He extends these undecidability results to classes with arbitrarily large constants (such as $P$). According to him, the answer to your question is that the language ($A$) is undecidable.

$\endgroup$
  • 1
    $\begingroup$ Your quantifiers appear in the wrong order: it should be $\exists k,C \forall x M(x) \text{ halts after at most $C|x|^k$ steps}$. $\endgroup$ – Yuval Filmus Sep 8 '13 at 23:19
  • $\begingroup$ @YuvalFilmus: You are correct. I have updated the answer to reflect this. Thanks for pointing this out. $\endgroup$ – mdxn Sep 8 '13 at 23:45

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.