Consider the well-known language: $$L = \{\langle M,x,1^t \rangle \ \ |\ \text{$M$ accepts $x$ after $t$ steps}\}$$

I've encountered some technical problem while trying to show a logarithmic reduction from some $L'\in P$ (which will show completeness of $L$)

Basically, the reduction is: $$f(x) = \langle M_{L'},x,n^c\rangle $$

Where $n^c$ is the time it takes for $M_{L'}$ to decide some input, $x$.

At first everything seems legitimate, but... How do we construct $M_{L'}$ at the first place?

In other words, do we have an "access" (as the reduction function) to the machine description?


You need to show that for every $L'\in P$ there exists a logspace reduction from $L'$ to $L$. Your $f$ has $\langle M_{L'}\rangle$ hardcoded into it. The encoding was part of its definition, $f$ does not ask what is the encoding of the machine for $L'$ when it tries to compute $f(x)$.

One way to think of this is as follows: consider the sequence of functions $\left\{f_{s ,c}\right\}_{c\in\mathbb{N}, s\in\{0,1\}^*}$ where $f_{s, c}(x)=\left(s, x, 1^{|x|^c}\right)$. Since $L'\in P$, there exists a function in this sequence which is a reduction from $L'$ to $L$ (the specific index depends on the machine deciding $L'$, but we don't really care about it).

  • $\begingroup$ Oh I see what made me confused about it. Thanks Ariel! $\endgroup$ – Covvar Jul 19 '17 at 20:06

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.