In these lecture notes the authors mentions that P is a syntactic complexity class, as we can find a decidable set of encodings for all polynomial time Turing machines. Of course, given a deterministic Turing machine $M$ and a number $k$, we can construct a Turing machine that simulates $M$ for $|x|^k$ steps on input $x$, and, if $M$ halts in these number of steps, returns the same answer as $M$. Now, every language in P is represented by such a Turing machine, and so, by encoding these Turing machines together with $k$ in a reasonable way, we have a decidable language representing P.

Then, the author defines $$ L = \{ \langle M, x \rangle \mid \mbox{$M$ is a polynomial-time Turing machine which accepts $x \in \{0,1\}^*$} \}, $$ and then claims that $L$ is in P. His argument is that we can first check that we have a valid encoding of $M$ and then run $M$ on input $x$. However, if I assume I have a Turing machine to decide $L$ in time $O(n^k)$ and $M$ is a Turing machine accepting a language in time $n^{k+1}$, then how can the original Turing machine run $M$ on inputs of length that need strictly more time on $M$ than the machine is allowed to run? I somehow think this "diagonalization" argument shows that $L$ could not be in P?

So, what am I missing? I tried to describe as precisely as possible how I understood the claims made, maybe I have understood something wrong...

  • 1
    $\begingroup$ The notes state that the fact that $M$ is a polynomial-time machine is enforced in the encoding of $M$ itself, for example by providing an upper bound on the running time of $M$ and forcing $M$ to either accept or reject if this upper bound is exceeded. You are essentially "promised" that any $M$ that can be properly encoded runs in polynomial-time. To decide $L$ you just have to check that the encoding of $M$ is valid and then simulate $M$ on $x$ until it eventually halts (after polynomially-many steps). $\endgroup$
    – Steven
    Jul 15, 2021 at 12:50
  • $\begingroup$ @Steven Yes, that remark I wanted to made more precise in my question. I mean, what I am doing is I am coding the machine together with a polynomial (I suspect hard-coding a threshold in form of a constant numbers makes no sense...). However, in this way, when I simulate $M$ it runs in polynomial time $O(n^{k_M})$ with $k_M$ depending on $M$. But I do not see how to find a uniform polynomial bound (working for every $M$ to simulate) for the machine that simulates the other poly-time machines? Sorry, still don't get it... $\endgroup$
    – StefanH
    Jul 15, 2021 at 13:10
  • $\begingroup$ The author is being sloppy. The construction works for a fixed bound on the running time of $M$. In contrast, bounding the running time by a fixed polynomial doesn't help you to decide the BPP analog. $\endgroup$ Jul 15, 2021 at 14:36
  • $\begingroup$ @StefanH. Good point, my argument is indeed incorrect $\endgroup$
    – Steven
    Jul 15, 2021 at 14:43
  • $\begingroup$ @Filmus That is actually a very weak statement then. As far as I can see, my argument shows that the language $L$ could not be in P at all. Is there a way to "rescue" the argument the author had in mind? I mean, I would call an argument only sloppy if the conclusion might be true, but if the conclusion could not be true at all, I would merely call it a false argument... $\endgroup$
    – StefanH
    Jul 15, 2021 at 14:49


Your Answer

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