Uogólnione twierdzenie Ladnera

45

Twierdzenie Ladnera stwierdza, że jeśli P ≠ NP, to istnieje nieskończona hierarchia klas złożoności ściśle zawierających P i ściśle zawartych w NP. Dowód wykorzystuje kompletność SAT przy wielu redukcjach NP. Hierarchia zawiera klasy złożoności skonstruowane przez rodzaj diagonalizacji, z których każda zawiera pewien język, do którego języków w niższych klasach nie da się zredukować wielokrotnie.

To motywuje moje pytanie:

Niech C będzie klasą złożoności, a D będzie klasą złożoności, która ściśle zawiera C. Jeśli D zawiera języki, które są kompletne dla pewnego pojęcia redukcji, to czy istnieje nieskończona hierarchia klas złożoności między C i D, w odniesieniu do zmniejszenie?

Mówiąc dokładniej, chciałbym wiedzieć, czy znane są wyniki dla D = P i C = LOGCFL lub C = NC , dla właściwego pojęcia redukcji.

Artykuł Ladnera zawiera już Twierdzenie 7 dla klas C ograniczonych przestrzenią, jak zauważył Kaveh w odpowiedzi. W najsilniejszej formie mówi to: jeśli NL ≠ NP, istnieje nieskończona sekwencja języków między NL i NP o ściśle rosnącej twardości. Jest to nieco bardziej ogólna niż zwykła wersja (Twierdzenie 1), która jest uzależniona od P ≠ NP. Jednak praca Ladnera rozważa tylko D = NP.

cc.complexity-theory reference-request np-intermediate

— András Salamon
źródło

1

Najpierw można zadać pytanie dotyczące klas, o których wiemy, że różnią się. Na przykład, czy istnieje nieskończona hierarchia między AC

a AC

[6] w odniesieniu do rzutów? To wygląda na trudne pytanie! :-)

^{0}

$^0$

^{0}

$^0$

— Michaël Cadilhac

Zobacz także cstheory.stackexchange.com/questions/52/…, aby uzyskać pytanie dotyczące odstępu od P do NP.

— András Salamon

33

Odpowiedź na twoje pytanie brzmi „tak” dla szerokiej gamy klas i redukcji, w tym redukcji przestrzeni logowej i klas, o których wspomniałeś, co zostało udowodnione w tych artykułach:

H. Vollmer. Powrócono do techniki luki w języku . Logika informatyki, Notatki z wykładów z informatyki Vol. 533, strony 389–399, 1990.

K. Regan i H. Vollmer. Języki luk i klasy złożoności czasu dziennika . Theoretical Computer Science, 188 (1-2): 101-116, 1997.

(Możesz pobrać spakowane pliki postscriptowe tych dokumentów tutaj .)

Dowody są zgodne z podstawową zasadą rozszerzenia twierdzenia Ladnera przez Uwe Schöninga:

Uwe Schöning. Jednolite podejście do uzyskiwania zestawów diagonalnych w klasach złożoności . Theoretical Computer Science 18 (1): 95-103, 1982.

Dowód Schöninga zawsze był moim ulubionym dowodem twierdzenia Ladnera - jest zarówno prosty, jak i ogólny.

— John Watrous
źródło

a co z lekcjami obietnicy?

— Marcos Villagra,

12

Jest bardzo prawdopodobne, że można to osiągnąć w ogólnych warunkach. Niemal na pewno taki wynik został już udowodniony w ogólnych ustawieniach, ale w tej chwili referencje mi uciekają. Oto argument od zera.

Zapis na stronie http://oldblog.computationalcomplexity.org/media/ladner.pdf zawiera dwa dowody twierdzenia Ladnera . Drugi dowód, autorstwa Russella Impagliazza, tworzy język w postaci { }, gdzie koduje zadowalającą formułę, a jest szczególną funkcją obliczaną w czasie wielomianowym. Oznacza to, że po prostu wypełniając SAT odpowiednią liczbą , możesz uzyskać zestawy „NP-pośrednie”. Wypełnienie wykonuje się w celu „przekątnej” wszystkich możliwych redukcji czasu wielomianu, tak aby nie było zmniejszenia wielomianu czasu z SAT do $L_1$ $x01^{f(|x|)}$ $x$ $f$ $1$ $L_1$ będzie działać (przy założeniu ). Aby udowodnić, że istnieje nieskończenie wiele stopni twardości, w powyższym argumencie należy zastąpić zamiast SAT i powtórzyć argument dla { }. Powtórz z { $P \neq NP$ $L_1$ $L_2 =$ $x 0 1^{f(|x|)} | x \in L_1$ $L_i =$ }. $x 0 1^{f(|x|)} | x \in L_{i-1}$

Wydaje się jasne, że taki dowód można uogólnić na klasy i , gdzie (1) jest odpowiednio zawarty w , (2) ma pełny język pod redukcjami, (3) lista wszystkich redukcji może być rekurencyjnie wyliczone, oraz (4) funkcji jest obliczeniowy w . Być może jedynym niepokojącym wymaganiem jest ostatni, ale jeśli spojrzysz na definicję w łączu, wygląda to bardzo łatwo obliczyć, dla najbardziej rozsądnych klas które mogę wymyślić. $C$ $D$ $C$ $D$ $D$ $C$ $C$ $f$ $C$ $f$ $C$

— Ryan Williams
źródło

8

Myślę, że odpowiedź jest pozytywna dla i jednolitej wersji . Dowód Ladnera nie wykorzystuje wiele innych niż to, co powiedziałeś, a fakt, że mniejsza klasa jest rekurencyjnie reprezentowana i powinna działać z drobnymi modyfikacjami, ale nie sprawdziłem szczegółów, spójrz na opis Lance'a tutaj . $C=L$ $NC$

Aktualizacja

Sprawdź artykuł Ladnera o strukturze wielomianowej redukcji czasu

Oto streszczenie: Dwa pojęcia wielomianowej redukowalności w czasie, oznaczone tutaj jako i , zostały zdefiniowane odpowiednio przez Cooka i Karpa. Badana jest abstrakcyjna właściwość tych dwóch relacji w dziedzinie zbiorów obliczalnych. Oba relacje okazują się gęste i mają minimalne pary. Ponadto istnieje ściśle rosnąca sekwencja z minimalną parą górnych granic sekwencji. Nasza metoda wskazywania gęstości daje wynik, że jeśli to istnieją elementy , które nie są wielomianami kompletne. $\leq_T^P$ $\leq_m^P$ $P \neq NP$ $NP - P$

Twierdzenie 1. Jeśli B jest obliczamy a nie w to istnieje obliczalną tak, że , i . $P$ $A$ $A \not \in P$ $A \leq_m^P B$ $B \not \leq_T^P A$

Zobacz także rozdział 6 omawiający uogólnienia:

Twierdzenie 5. Jeśli jest klasa czas potem i są zwrotne i przechodnie relacje i twierdzenia 1-4 hold z zastąpione . $C$ $\leq_m^C$ $\leq_T^C$ $P$ $C$

Twierdzenie 7. Jeżeli jest klasa przestrzeń następnie i są zwrotne i przechodnie relacje i twierdzenia 1-4 hold z zastąpione . $C$ $\leq_m^C$ $\leq_T^C$ $P$ $C$

Pojęcia klasa czasu i klasa przestrzeni są zdefiniowane w artykule.

— Kaveh
źródło

Sposób, w jaki rozumiałem dowody Ladnera i Impagliazza, wydawał się wykorzystywać pewne składniki specyficzne dla NP, SAT i wielokrotne redukcje czasu wielomianowego. Moje pytanie ma dokładnie dotyczyć tego, czy składniki te można stosować bardziej ogólnie.

— András Salamon

@ András Salamon: Nie, tak naprawdę oryginalny dowód Ladnera nie wykorzystuje żadnego faktu na temat SAT, że można go obliczyć (patrz twierdzenie 1 powyżej). W części 6 omawia właściwości wymagane do redukcji dla swoich twierdzeń. Myślę, że

to klasa kosmiczna.

L

$L$

— Kaveh

Myślę, że twierdzenie to można również uogólnić na jednolite klasy obwodów, więc twierdzenie 1 będzie również działać dla

(nie sprawdziłem szczegółów, dodam je do postu, kiedy to zrobię lub znajdę referencję), ale nie nie sądzę, że można go uogólnić na wersje niejednorodne, ponieważ dowód wykorzystuje fakt, że klasa złożoności jest rekurencyjnie reprezentowana. Interesujące byłoby wiedzieć, czy twierdzenie 1 dotyczy także

(wersja jednolita), co odpowiadałoby na komentarz Michaëla Cadilhaca pod postem.

C = N C

$C=NC$

C = A C^{0}

$C=AC^0$

— Kaveh

5

Poprosiłem podobne pytanie do Peter Shor w Mathoverflow tutaj . Według niego nie jest świadomy takiego wyniku.

$NP\neq P$

$A$ $\sum_i^p$ $B \in \sum_{i-1}^p$ $B$

Innym interesującym problemem jest rozważenie uogólnienia Ladnera na obiecujące wersje klas semantycznych, takie jak promiseBPP, promiseMA itp.

— Marcos Villagra
źródło

Zapomniałem wspomnieć, że dotyczy to oczywiście tylko PH i wydaje się, że jest to bardziej prawdopodobne podejście niż przyjęcie jakiejkolwiek klasy złożoności.

— Marcos Villagra,

5

Link: mathoverflow.net/questions/9221/…

— Ryan Williams

3

C

$C$

B P P

$BPP$

M A

$MA$

N C

$NC$

tak, wyliczenie maszyn z klas semantycznych nie jest rekurencyjne. Ale obiecujące wersje klas semantyki (promiseBPP, promiseMA, ...) są rzeczywiście sintaktyczne.

— Marcos Villagra,