Uogólnione twierdzenie Ladnera

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.

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.

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 { x 01 f ( | x | ) }, gdzie x koduje zadowalającą formułę, a f jest szczególną funkcją obliczaną w czasie wielomianowym. Oznacza to, że po prostu wypełniając SAT odpowiednią liczbą 1 , 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 $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ć L 1 zamiast SAT i powtórzyć argument dla L 2 = { x 0 1 f ( | x | ) | x ∈ L 1 }. Powtórz z L i = { x 0 1 f ( | x | ) | x ∈ L i $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 D , gdzie (1) C jest odpowiednio zawarty w D , (2) D ma pełny język pod C- redukcjami, (3) lista wszystkich C- redukcji może być rekurencyjnie wyliczone, oraz (4) funkcji f jest obliczeniowy w C . Być może jedynym niepokojącym wymaganiem jest ostatni, ale jeśli spojrzysz na definicję f w łączu, wygląda to bardzo łatwo obliczyć, dla najbardziej rozsądnych klas C, które mogę wymyślić.$C$$D$$C$$D$$D$$C$$C$$f$$C$$f$$C$

Myślę, że odpowiedź jest pozytywna dla i jednolitej wersji N C . 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 ≤ P m , 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 P ≠ N P, to istnieją elementy N P - P , 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ą A tak, że ∉ P , ≤ P m B i B ≰ P T .$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 ≤ C m i ≤ C T są zwrotne i przechodnie relacje i twierdzenia 1-4 hold z P zastąpione C .$C$$\leq_m^C$$\leq_T^C$$P$$C$

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

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

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.