25
$\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$
9
  • 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$ Commented Aug 8, 2013 at 20:44
  • 4
    $\begingroup$ I think all famous NP-complete problems are actually complete under many-one AC0 reductions. $\endgroup$
    – Kaveh
    Commented Aug 9, 2013 at 7:21
  • 1
    $\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$ Commented Aug 14, 2013 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$ Commented Aug 15, 2013 at 2:18
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Aug 16, 2013 at 10:47

2 Answers 2

27
$\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$
1
  • $\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$ Commented Aug 14, 2013 at 21:22
-3
$\begingroup$

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}

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 25, 2022 at 8:39
  • $\begingroup$ 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. $\endgroup$ Commented Jan 25, 2022 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.