# Upper bound for the time complexity of a TM in P on input x?

I am trying to show that the following problem is P-complete with respect to LOGSPACE reductions: given a Turing machine $M^*$, an input $x$ for that machine, and a number $t$ in unary, does $M^*$ accept $x$ in $t$ steps?

To do that I want to compute an upper bound on the time complexity of some TM $M$ in P on input $x$. I tried to use the maximum number of configurations, but failed because I don't know the space complexity either - I only know that space and time complexities are polynomial.

The complexity class P is a set of languages, not a set of Turing machines. A language is in P if it is accepted by some Turing machine running in polynomial time. So for every language $L$ in P, there is a Turing machine $M$ that accepts $L$ and runs in time $p(n)$ for some polynomial $p$, where $n$ is the input length. This is exactly the time bound you're after — its existence is guaranteed by the definition of P.

To show that the problem you were given is P-complete, you need to show that every language in P reduces to your problem. In other words, you need to show that for all languages $L \in P$ there exists a polytime reduction from $L$ to your problem. The reduction accepts an instance of $L$, and can depend on $L$ arbitrarily.

What you seem to be trying to construct is a function with two inputs: a language $L \in P$ (given as a polytime Turing machine) and an instance $x$ of $L$. There is absolutely no need to construct such a function.

• My problem is that in the reduction, for $L$ in $P$ and $M$ the TM of $L$ that runs in polynomial time, I need (?) to compute $p(n)$ from $M$ and $x$. I don't think I can simulate $M$ on $x$ because that's at least linear space?
– Bar
May 7, 2017 at 18:23
• No you don't. To prove that the problem you were given is P-complete wrt logspace reductions, you need to show that each problem in P reduces (in logspace) to your problem. There is no need to construct a function that takes a Turing machine and outputs a reduction. All you need to do is prove "$\forall L \in P \exists \textit{reduction}$". May 7, 2017 at 19:22
• Ah, now I get it. Seems like I was trying to prove the wrong thing. The only 'real' work the function needs to do is compute p(n) for n = |x|, because for a given L, I know the corresponding M and p . And that can easily be done in logspace...
– Bar
May 7, 2017 at 20:23
• I think the title should be changed, not sure how to describe the problem shortly though.
– Bar
May 7, 2017 at 20:25
• Well, that was your original question, which the title describes well enough. The answer is that you don't need this a priori time bound after all. May 7, 2017 at 20:27