# 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?

• P reduction means polynomial time computable many-one function or AKA as Karp reduction. – Mohammad Al-Turkistany Aug 8 '13 at 18:52
• 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. – Marzio De Biasi Aug 8 '13 at 20:44
• I think all famous NP-complete problems are actually complete under many-one AC0 reductions. – Kaveh Aug 9 '13 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. – David Richerby Aug 14 '13 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$? – Mohammad Al-Turkistany Aug 15 '13 at 2:18

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...)