Is finding Logspace reductions harder than P reductions?

Question

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?

Answer 1

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

Answer 2

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}