20
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ P reduction means polynomial time computable many-one function or AKA as Karp reduction. $\endgroup$ – Mohammad Al-Turkistany Aug 8 '13 at 18:52
  • 4
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Aug 8 '13 at 20:44
  • 3
    $\begingroup$ I think all famous NP-complete problems are actually complete under many-one AC0 reductions. $\endgroup$ – Kaveh Aug 9 '13 at 7:21
  • $\begingroup$ 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. $\endgroup$ – David Richerby Aug 14 '13 at 14:10
  • 1
    $\begingroup$ What is the proof that logspace reductions are harder than P reductions? How can you do it without separating $L$ from $P$? $\endgroup$ – Mohammad Al-Turkistany Aug 15 '13 at 2:18
20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Aug 14 '13 at 21:22
  • $\begingroup$ Natural problem in the most common interpretation of the word natural in complexity theory. $\endgroup$ – Mohammad Al-Turkistany Aug 14 '13 at 21:31

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.