# A synctactic property of the complexity class P

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...

• 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). Jul 15 '21 at 12:50
• @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... Jul 15 '21 at 13:10
• 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. Jul 15 '21 at 14:36
• @StefanH. Good point, my argument is indeed incorrect Jul 15 '21 at 14:43
• @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... Jul 15 '21 at 14:49