L / P / PSpace vs P / NP

w 1979 r. Hopcroft / Ullman napisał, że L ⊆ P ⊆ NP ⊆ PSpace jest znany, ale L ⊊ PSpace jest jedynym właściwym (i trywialnym) zabezpieczeniem znanym, chociaż wszystkie są przypuszczane, że są odpowiednimi zabezpieczeniami i „tam, gdzie rzeczy nadal istnieją” ~ 4 dekady później .

od tego czasu istnieje jakieś znane połączenie między L ⊊ P, P ⊊ PSpace a P ⊊ NP? czy wszyscy są nadal uważani za niezależnych, czy też są jakieś oznaki pewnej współzależności?

Uzasadnienie: to pytanie jest częściowo inspirowany przez ostatnich wyników Backurs-indyk wiążących Seth O (n- ² ) edycji odległość. SETH to czas wykładniczy, a odległość edycji to PTime. (a także nieco pytanie potwierdzające dolne granice przez udowodnienie górnych granic )

$L \subsetneq PSPACE$

Niedawne prace nad `` Złożonością drobnoziarnistą '', takie jak wynik Edycja odległości Backurs i Indyk, pomijają fakt, że nie jesteśmy w stanie udowodnić prawidłowego zabezpieczenia, takiego jak . W szczególności SETH jest znacznie silniejszy hipoteza niż , mniej więcej stwierdzając, że CNF-SAT wymaga czasu (nie tylko czasu super-wielomianowego). Przy tej silniejszej hipotezie można wykazać redukcję z CNF- SAT dla problemów w (np. Edytuj odległość), a następnie otrzymujesz warunkową dolną granicę na podstawie SETH. Tak więc rozróżnienia, których dotyczą te prace (tj. vs.$P\neq NP$$P \neq NP$$2^n$$2^{n/k}$$P$$\Omega(n^k)$$2^{n}$$2^{(1-\delta)n}$) są znacznie ściślejsze niż różnice między tradycyjnymi klasami złożoności wspomnianymi w poście.

Podobnie, w celu udowodnienia niższych granic obwodu poprzez szybsze algorytmy satysfakcji, na ogół potrzebujemy tylko drobnoziarnistych ulepszeń w stosunku do trywialnych algorytmów , aby uzyskać niższe granice. Na przykład algorytm dla CircuitSAT na obwodach bramek okazałby się .$O^\star(2^n)$$2^{n}poly(n^k)/n^{\omega(1)}$$n^k$$NEXP \not \subseteq P/poly$