1
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Bar May 7 '17 at 18:23
  • $\begingroup$ 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}$". $\endgroup$ – Yuval Filmus May 7 '17 at 19:22
  • $\begingroup$ 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... $\endgroup$ – Bar May 7 '17 at 20:23
  • $\begingroup$ I think the title should be changed, not sure how to describe the problem shortly though. $\endgroup$ – Bar May 7 '17 at 20:25
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 7 '17 at 20:27

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.