# 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? – Gray May 7 '17 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}$". – Yuval Filmus May 7 '17 at 19:22