# Is finding Logspace reductions harder than P reductions?

Motivated by Shor's answer related to different notions of NP-completeness, I am looking for a problem that is NP-complete under P reductions but not known to be NP-complete under Logspace reductions (preferably for a long time). Also, Is finding Logspace reductions between NP-complete problems harder than finding P reductions?

• I think that it is an open problem ... and the !!!non-authoritative!!! Wikipedia :-) :-) agrees: "... It is an open question if the NP-complete problems are different with respect to log-space and polynomial-time reductions ...". See also Pebbles and Branching Programs for Tree Evaluation for a recent attempt to separate L and P. Commented Aug 8, 2013 at 20:44
• I think all famous NP-complete problems are actually complete under many-one AC0 reductions. Commented Aug 9, 2013 at 7:21
• It's trivially harder to find logspace reductions than polytime reductions because logspace is more restrictive. Having said that, a lot of the polytime reductions you see do only use logarithmic space. Commented Aug 14, 2013 at 14:10
• What is the proof that logspace reductions are harder than P reductions? How can you do it without separating $L$ from $P$? Commented Aug 15, 2013 at 2:18
• @Mohammad If $L$ is strictly less powerful than $P$, you need more skill (i.e., it is harder) to implement a given reduction in logspace than polytime. Commented Aug 16, 2013 at 10:47

Kaveh is correct in saying that all of the "natural" NP-complete problems are easily seen to be complete under (uniform) $\mathrm{AC}^0$ reductions. However, one can construct sets that are complete for NP under logspace reductions that are not complete under $\mathrm{AC}^0$ reductions. For instance, in [Agrawal et al, Computational Complexity 10(2): 117-138 (2001)) an error-correcting encoding of SAT was shown to have this property.

As regards a "likely" candidate for a problem that is complete under poly-time reductions but not under logspace reductions, one can try to cook up an example of the form {$(\phi,b)$ : $\phi$ is in SAT and $z$ is in CVP [or some other P-complete set] iff $b=1$, where $z$ is the string that results by taking every 2nd bit of $\phi$}. Certainly the naive way to show that this set is complete will involve computing the usual reduction to SAT, and then constructing $z$ and computing the bit $b$, which is inherently poly-time. However, with a bit of work, schemes such as this can usually be shown to be complete under logspace reductions via some non-naive reduction. (I haven't worked out this particular example...)

• Thanks for your nice answer and I love accepting it but I will wait for an answer that addresses directly my question with a natural problem. Commented Aug 14, 2013 at 21:22

A language $$L$$ is in $$NP$$ when there is a language $$L'$$ in $$P$$ and a polynomial $$p$$ with $$L = \{ x | \exists y \ in \{0,1\}^{p(|x|)} \text{ with } (x,y) \in L' \}$$ (see: a standard text on complexity theory, e.g. Wegener: Komplexitätstheorie, Berlin 2005)

One can choose the language $$L'$$ such that it can be decided by a logspace TM.

Lemma: For any language $$L$$ in NP there is a TM $$M$$ with $$L = \{ x \mid \exists u \in\{0,1\}^* M \text{ accepts } x\#u \text{ with at most } O(\log(|x|)) \text{ tape space} \}$$

Proof: If $$L$$ is in NP, then there is a TM $$M$$ with $$L = \{ x \mid \exists u \in\{0,1\}^* M \text{ accepts } x \text{ within } T = p(|x|) \text{ steps } \}$$ where $$p$$ is a polynomial. The length of $$u$$ and the used space on the working tape are less than $$T$$.

Let $$S = (s_{i,j}) \in \{0,1\}^{T \times T}$$ a matrix with $$s_{i,j}$$ is the value of the $$i^{th}$$ bit of the tape space at step $$j$$. $$L$$ can also be written as $$L = \{ x \mid \exists u \in\{0,1\}^* \exists s \in\{0,1\}^{T \times T} :M' \text{ accepts } x\#u\#s \text{ with at most }O(\log|x|)) \text{ tape space} \}$$.

$$M'$$ simulates $$M$$ in the following way:

$$h$$ is the position of the read-write head at start.
check if $$s_{0,0},...,s_{T,0}$$ is the working tape space of $$M$$ at start.
for $$t$$ in $$1,..,T$$ do
check if $$s_{h,t}$$ has the value, that $$M$$ writes on the tape at step $$t$$
If $$M$$ moves the read-write-head of the working tape the left then $$h := h-1$$
else if $$M$$ moves the read-write-head to the right then $$h:= h+1$$
for i in $$1,...,T$$ do
check if $$s_{i,t} = s_{i,t_1} when$$i != h$done done  QED Due to this lemma, any language in $$NP$$ can be reduced to a $$NP$$-complete language with a logspace reduction. Corollary: L^{NP} = P^{NP} • The corollary is not true, or at least not known. The class$L^{NP}$is known as$\Theta_2^P$, and is the same as$P$with logarithmically many queries to an$NP$oracle, or$P$with parallel, non-adaptive queries to an$NP$oracle. Whether or not this class is the same as$\Delta_2^P = P^{NP}\$ is an open problem. Commented Jan 25, 2022 at 8:39
• Yes, every NP language has a logspace reduction to some NP-complete problem. In fact, it is well known, and already noted in Kaveh’s answer, that there exist languages NP-complete under logspace (or even AC^0 or DLOGTIME) reductions, and that most natural NP-complete problems already have this property. However, this does not in any way answer the question, and in particular, it shows no light on the problem whether all languages NP-complete under ptime reductions are also NP-complete under logspace reductions. Commented Jan 25, 2022 at 9:35