Czy znalezienie redukcji Logspace jest trudniejsze niż redukcji P?

Zmotywowani odpowiedzią Shora związaną z różnymi pojęciami kompletności NP, szukam problemu, który jest NP-kompletny przy redukcjach P, ale nie jest znany jako NP-kompletny przy redukcjach Logspace (najlepiej przez długi czas). Ponadto, czy znalezienie redukcji Logspace między problemami NP-zupełnymi jest trudniejsze niż znalezienie redukcji P?

cc.complexity-theory np-hardness

— Mohammad Al-Turkistany
źródło

Redukcja P oznacza wielomianową funkcję obliczaną w czasie wieloczynnikowym lub AKA jako redukcję Karp.

— Mohammad Al-Turkistany

Myślę, że jest to problem otwarty ... i !!! nieautorytatywny !!! Wikipedia :-) :-) zgadza się: „... Pytanie jest otwarte, czy problemy NP-zupełne różnią się w odniesieniu do przestrzeni logów i redukcji czasu wielomianowego ...”. Zobacz także Kamyki i programy rozgałęziające do oceny drzewa, aby dowiedzieć się o ostatniej próbie oddzielenia L i P.

— Marzio De Biasi

Myślę, że wszystkie znane problemy z kompletnym NP są w rzeczywistości zakończone przy wielu redukcjach AC0.

— Kaveh

Zmniejszenie przestrzeni logicznej jest o wiele trudniejsze niż redukcja czasu przestoju, ponieważ przestrzeń logiczna jest bardziej restrykcyjna. To powiedziawszy, wiele widocznych redukcji czasu przestoju wykorzystuje tylko przestrzeń logarytmiczną.

— David Richerby

Jaki jest dowód, że redukcje przestrzeni logicznej są trudniejsze niż redukcje P? Jak możesz to zrobić bez oddzielania

L

$L$

P

$P$

— Mohammad Al-Turkistany

$\mathrm{AC}^0$ $\mathrm{AC}^0$

$(\phi,b)$ $\phi$ $z$ $b=1$ $z$ $\phi$ $z$ $b$ , co z natury jest wielopłaszczyznowe. Jednak przy odrobinie pracy schematy takie jak ten zazwyczaj można wykazać jako zakończone w ramach redukcji przestrzeni logicznej poprzez pewną nieinwazyjną redukcję. (Nie opracowałem tego konkretnego przykładu ...)

— Eric Allender
źródło

Dziękuję za miłą odpowiedź i uwielbiam ją przyjmować, ale poczekam na odpowiedź, która bezpośrednio odpowie na moje pytanie z naturalnym problemem.

— Mohammad Al-Turkistany

Problem naturalny w najczęstszej interpretacji słowa naturalna w teorii złożoności.

— Mohammad Al-Turkistany