<p>A language <span class="math-container">$L$</span> is in <span class="math-container">$NP$</span> when there is a language <span class="math-container">$L'$</span> in <span class="math-container">$P$</span> and a polynomial <span class="math-container">$p$</span> with
<span class="math-container">$L = \{ x | \exists y \ in \{0,1\}^{p(|x|)} \text{ with } (x,y) \in L' \}$</span>
(see: a standard text on complexity theory, e.g. Wegener: Komplexitätstheorie, Berlin 2005)</p>
<p>One can choose the language <span class="math-container">$L'$</span> such that it can be decided by a logspace TM.</p>
<p>Lemma: For any language <span class="math-container">$L$</span> in NP there is a TM <span class="math-container">$M$</span> with
<span class="math-container">$L = \{ x \mid \exists u \in\{0,1\}^* M \text{ accepts } x\#u \text{ with at most } O(\log(|x|)) \text{ tape space} \}$</span></p>
<p>Proof: If <span class="math-container">$L$</span> is in NP, then there is a TM <span class="math-container">$M$</span> with
<span class="math-container">$L = \{ x \mid \exists u \in\{0,1\}^* M \text{ accepts } x \text{ within }
T = p(|x|) \text{ steps } \}$</span> where <span class="math-container">$p$</span> is a polynomial.
The length of <span class="math-container">$u$</span> and the used space on the working tape are less than <span class="math-container">$T$</span>.</p>
<p>Let <span class="math-container">$S = (s_{i,j}) \in \{0,1\}^{T \times T}$</span> a matrix with
<span class="math-container">$s_{i,j}$</span> is the value of the <span class="math-container">$i^{th}$</span> bit of the tape space at step <span class="math-container">$j$</span>.
<span class="math-container">$L$</span> can also be written as
<span class="math-container">$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} \}$</span>.</p>
<p><span class="math-container">$M'$</span> simulates <span class="math-container">$M$</span> in the following way:</p>
<pre><code><span class="math-container">$h$</span> is the position of the read-write head at start.
check if <span class="math-container">$s_{0,0},...,s_{T,0}$</span> is the working tape space of <span class="math-container">$M$</span> at start.
for <span class="math-container">$t$</span> in <span class="math-container">$1,..,T$</span> do
   check if <span class="math-container">$s_{h,t}$</span> has the value, that <span class="math-container">$M$</span> writes on the tape at step <span class="math-container">$t$</span>
   If <span class="math-container">$M$</span> moves the read-write-head of the working tape the left then <span class="math-container">$h := h-1$</span> 
   else if <span class="math-container">$M$</span> moves the read-write-head to the right then <span class="math-container">$h:= h+1$</span>
   for i in <span class="math-container">$1,...,T$</span> do
     check if <span class="math-container">$s_{i,t} = s_{i,t_1} when $</span>i != h$
   done
done
</code></pre>
<p>QED</p>
<p>Due to this lemma, any language in <span class="math-container">$NP$</span> can be reduced to a <span class="math-container">$NP$</span>-complete language with a
logspace reduction.</p>
<p><strike>Corollary: L^{NP} = P^{NP} </strike></p>

CC BY-SA 4.0
2022-01-25T08:39:39.177Z
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.
Jan Johannsen
CC BY-SA 4.0
2022-01-25T09:35:58.377Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-01-24T14:34:41.053Z
2024-02-13T10:52:27.800Z
2024-02-13T10:52:27.800Z
Reiner Czerwinski
<p>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.</p>

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

CC BY-SA 3.0
2013-08-14T21:22:22.957Z
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.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-08-13T23:21:35.603Z
2013-08-14T15:12:15.113Z
2013-08-14T15:12:15.113Z
Eric Allender
<p>Motivated by <a href="https://cstheory.stackexchange.com/a/18580/495">Shor's answer</a> 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>

CC BY-SA 3.0
2013-08-08T18:52:40.467Z
P reduction means polynomial time computable many-one function or AKA as Karp reduction.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-08-08T20:44:53.393Z
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](http://arxiv.org/abs/1005.2642) for a recent attempt to separate L and P.
Marzio De Biasi
CC BY-SA 3.0
2013-08-09T07:21:16.680Z
I think all famous NP-complete problems are actually complete under many-one AC0 reductions.
Kaveh
CC BY-SA 3.0
2013-08-14T14:10:07.430Z
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
CC BY-SA 3.0
2013-08-15T02:18:48.927Z
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
CC BY-SA 3.0
2013-08-15T12:38:04.503Z
There's no proof that it's _strictly_ harder but it has to be at least as hard; under the widely held assumption that $L\neq P$, it is strictly harder. I didn't expect to have to spell that out, here.
David Richerby
CC BY-SA 3.0
2013-08-16T01:09:33.563Z
@DavidRicherby Your claim is incorrect. $L \ne P$ implies that problems in $L$ are easier than problem in $P$ since class $L$ is contained in $P$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-08-16T10:47:35.837Z
@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.
David Richerby
CC BY-SA 3.0
2013-08-20T14:10:26.247Z
"It is open whether NP-complete problems under the two definitions [P reductions and logspace reductions] coincide." -- C. Papadimitriou, "Computational Complexity" (1994)
dd1
<cc.complexity-theory><np-hardness>
Is finding Logspace reductions harder than P reductions?
Mohammad Al-Turkistany
# Is finding Logspace reductions harder than P reductions?

(Asked by: username_0 on 2013-08-08)

Motivated by [Shor's answer](https://cstheory.stackexchange.com/a/18580/495) 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?

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_0**: P reduction means polynomial time computable many-one function or AKA as Karp reduction.  
> **username_1**: 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](http://arxiv.org/abs/1005.2642) for a recent attempt to separate L and P.  
> **username_2**: I think all famous NP-complete problems are actually complete under many-one AC0 reductions.  
> **username_3**: 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.  
> **username_0**: What is the proof that logspace reductions are harder than P reductions? How can you do it without separating $L$ from $P$?  
> **username_3**: There's no proof that it's _strictly_ harder but it has to be at least as hard; under the widely held assumption that $L\neq P$, it is strictly harder. I didn't expect to have to spell that out, here.  
> **username_0**: @DavidRicherby Your claim is incorrect. $L \ne P$ implies that problems in $L$ are easier than problem in $P$ since class $L$ is contained in $P$.  
> **username_3**: @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.  
> **username_4**: "It is open whether NP-complete problems under the two definitions [P reductions and logspace reductions] coincide." -- C. Papadimitriou, "Computational Complexity" (1994)  

---

## 2 answers

### Answer by username_8 on 2013-08-13. Score: 27 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_5 on 2022-01-24. Score: -3

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}

> **Comments:**
> **username_6**: 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.  
> **username_7**: 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.  

---

