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?
Is finding Logspace reductions harder than P reductions?
cc.complexity theory;np hardness
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...)