0
$\begingroup$

Generally, I want to use the diagonal argument to prove it. I tried to define a language $A$ which is constructed by a Turing machine $D$:

It will only take a input which has a form of a Turing machine $\langle M\rangle$ (the description of $M$) and simulate $M$ on $\langle M\rangle$. If it halts in polytime and accept, reject. If it halts in polytime and reject, accept.

If $A$ is in P, there must exist a Turing machine $M'$ that decides it in polytime. However, if I run $D$ on the input $\langle M'\rangle$, the result will be converse to the simulation. Contradiction! So $A$ should not be in P.

The problem is that I don't know whether a turing machine will halt in polytime or not. Polytime can be $n^2$, $n^3$, $n^4$, ...

Improve this question
$\endgroup$
5
  • $\begingroup$ Use the time hierarchy theorem with any time bound that is super-polynomial. $\endgroup$
    – Yuval Filmus
    Apr 22, 2017 at 7:00
  • $\begingroup$ You may avoid the hierarchy theorem here. The proof is basically correct: the missing point is that you can give an effective enumeration of machines for P, and then you can diagonalize on such an enumeration. $\endgroup$
    – Andrea Asperti
    Apr 23, 2017 at 18:33
  • $\begingroup$ @AndreaAsperti How can I construct the enumeration of machines for P? I know that if a language is semi-decidable then I can enumerate the language. So what you said was I need to construct a language A = {<M>|M will halt all inputs in polytime}. But is A semi-decidable? How can I prove it? $\endgroup$
    – TIANLUN ZHU
    Apr 25, 2017 at 18:34
  • $\begingroup$ @TIANLUNZHU A simple way is to define the language as pairs <M,P> where M is a traditional TM and P is a polynomial used as a timer. Any polynomial algorithm can be computed by a program in the previous language. But there are many alternative languages that are P-complete. Diagonalization proves that the interpreter for such languages cannot be in P. A property that is true for any subrecursive language, in fact. $\endgroup$
    – Andrea Asperti
    Apr 25, 2017 at 21:14
  • $\begingroup$ Please, have a look at my answer at the following question for more details stackoverflow.com/questions/5018359/… $\endgroup$
    – Andrea Asperti
    Apr 25, 2017 at 21:26

2 Answers 2

Reset to default
2
$\begingroup$

Unfortunately, this doesn't work at all. What you're proposing to do is to simulate a Turing machine on some input, and ask whether it accepts/rejects that input in polynomial time, and that question is not well-formed.

"Polynomial time" is the class P of Turing machines $M$ that have the following property: there is are constants $c$ and $k$ such that, for every input of length $n$, $M$ halts in at most $cn^k$ steps. Notice that this property talks about all inputs, so you can't test it just by looking at one input.

Indeed, it doesn't make sense to ask if a particular input is "accepted in polynomial time." Let the input have length $n$ and suppose that the Turing machine takes $t$ steps to accept it. We can always find constants such that $t\leq cn^k$. For example, we could take $c=t$ and $k=0$.

You need to look at the time hierarchy theorem which says, loosely, that Turing machines with longer running time can decide more languages than Turing machines with shorter running times. Its proof does indeed use diagonalization, so you started with the right idea.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah, I know the idea of time hierarchy theorem. However, the original question asks me to prove this by using "idea" of proving hierarchy theorem. Also, it says "don't use time hierarchy theorem directly". What should I do... $\endgroup$
    – TIANLUN ZHU
    Apr 24, 2017 at 19:47
0
$\begingroup$

One problem is that for time hierarchy you have to increase the class by a logarithmic factor to obtain new languages since the simulation introduces a logarithmic time overhead (unless you come up with something more efficient). Instead, we prove P is properly contained in EXP with a diagonal argument. Define language A that is decidable in $O(2^n)$ but not in $o((2^n)/n)$. We define A as the language decided by D where D is defined as follows:

D= "on input w:
    Store ceiling(2^n/n) in a binary counter. 
    #We can do this in O(2^n) because of time constructability
    Now, on each following step, decrement the counter and if it reaches 0 reject.
    If w doesn't have form <M>01* for some M that is TM, reject.
    Simulate M on w and reject if it accept, accept if it rejects."

So the counter's length is approximately $log(2^n/n)\in O(n)$ and the simulation adds a cost in $O(2^n/n)$ so we can give bound D's runtime above in $O(2^n)$. So A is in EXPTIME.

For contradiction, assume $A\in P$. Then $A \in Time(o(2^n/n))$. Let M be a TM such that M decides A in $o(2^n/n)$ , then D can simulate M in time $t(n)=d\cdot o(2^n/n)$ for some constant d. Then, $\exists n_0,\forall n>n_0, t(n)<2^n/n$ by definition of $o$. Then, the simulation in D will get to the last line without timing out for M on w if $||w||>n_0$. Now, run D on $w=<M>01^{n_0}$ so the input is large enough. Now, D will do the opposite of M so M cannot decide A, since A is defined as the language decided by D, which is the contradiction we wanted. Therefore, we conclude $A\notin P$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't understand the "problem" you're talking about with the time hierarchy theorem. You've proven a weaker version of the theorem. That's not a "problem" with the theorem, but a strength: the time hierarchy theorem is so good that even a weakened version of it is enough to prove what we want here. $\endgroup$
    – David Richerby
    Apr 23, 2017 at 13:10
  • $\begingroup$ I didn't say it was a problem with the time hierarchy theorem. The poster wanted to use diagonalization like in that of the proof of time hierarchy theorem. The "problem" refers to the fact that we cannot prove proper containment for time hierarchy using diagonalization without increasing the time complexity class by logarithmic factor, which makes it harder than space hierarchy using diagonalization. What is the stronger version of the theorem you are referring to? $\endgroup$
    – user152152
    May 7, 2017 at 15:34
  • $\begingroup$ The standard version of the time hierarchy theorem shows that, for any function $f$, there is a langauge decidable in $\mathrm{Time}[O(f(n)]$ but not in $\mathrm{Time}[o(f(n)/\log n)]$. You've proven that, for a specific choice of $f$, there is a language decidable in $\mathrm{Time}[f(n)]$ but not in $\mathrm{Time}[o(f(n)/n]$. That is, you've weakened both the hypothesis (general $f$ to specific $f$) and the conclusion ($f/\log n$ to $f/n$). Time hierarchy gives a logarithmic factor, but your version has a linear factor. $\endgroup$
    – David Richerby
    May 7, 2017 at 18:28
  • 1
    $\begingroup$ Oh, okay, I understand what you meant. The proof does do exactly what the poster wanted though, which is to show there is a decidable language not in P, so I just hope he/she took the time to read it. Unlikely though, considering it was asked the night before their exam, sigh. $\endgroup$
    – user152152
    May 9, 2017 at 1:32

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.