L / P / PSpace vs P / NP

12

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

vzn
źródło

Odpowiedzi:

8

L.P.S.P.ZAdomi

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.N.P.P.N.P.2)n2)n/kP.Ω(nk)2)n2)(1-δ)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(2)n)2)npoly(nk)/nω(1)nkN.miXP.P./poly

palindrom
źródło
Jak to odpowiada na pytanie, które dotyczy implikacji (lub „współzależności”, cokolwiek to może znaczyć) między trzema stwierdzeniami?
András Salamon,
Chciałem odpowiedzieć na pytanie w oparciu o jego uzasadnioną motywację. Nie jestem osobiście świadomy żadnych nietrywialnych „współzależności” między stwierdzeniami.
palindrom