Ist es schwieriger, Logspace-Reduzierungen zu finden als P-Reduzierungen?

Motiviert durch Shors Antwort zu verschiedenen Begriffen der NP-Vollständigkeit suche ich nach einem Problem, das unter P-Reduktionen NP-vollständig ist, unter Logspace-Reduktionen jedoch (vorzugsweise für längere Zeit) nicht als NP-vollständig bekannt ist. Ist es auch schwieriger, Logspace-Reduzierungen zwischen NP-vollständigen Problemen zu finden, als P-Reduzierungen zu finden?

Kaveh sagt zu Recht, dass alle "natürlichen" NP-vollständigen Probleme bei (gleichmäßigen) -Reduktionen leicht als vollständig angesehen werden können . Man kann jedoch Mengen erstellen, die für NP unter logspace reductions vollständig sind, die unter A C 0 nicht vollständig sind$\mathrm{AC}^0$$\mathrm{AC}^0$ -Reduktionen . Beispielsweise wurde in [Agrawal et al., Computational Complexity 10 (2): 117-138 (2001)] gezeigt, dass eine fehlerkorrigierende Kodierung von SAT diese Eigenschaft aufweist.

In Bezug auf einen "wahrscheinlichen" Kandidaten für ein Problem, das unter Mehrfachzeitverkürzungen, aber nicht unter Logspace-Verkürzungen vollständig ist, kann man versuchen, ein Beispiel für die Form { : ϕ ist in SAT und z ist in CVP [oder eine andere P-vollständige Menge] iff b = 1 , wobei z die Zeichenfolge ist, die sich ergibt, wenn jedes zweite Bit von ϕ } genommen wird. Der naive Weg, um zu zeigen, dass diese Menge vollständig ist, besteht sicherlich darin, die übliche Reduktion auf SAT zu berechnen und dann z zu konstruieren und das Bit b zu berechnen$(\phi,b)$$\phi$$z$$b=1$$z$$\phi$$z$$b$, die von Natur aus Poly-Zeit ist. Mit ein wenig Arbeit kann jedoch gezeigt werden, dass Schemata wie dieses normalerweise vollständig sind, wenn der Logspace durch eine nicht-naive Reduktion reduziert wird. (Ich habe dieses spezielle Beispiel nicht ausgearbeitet ...)