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.


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 0 a AC 0 [6] w odniesieniu do rzutów? To wygląda na trudne pytanie! :-)00
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

Odpowiedzi:


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.


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 { 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 1L1x01f(|x|)xf1L1bę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 -PNPL1L2=x01f(|x|)|xL1Li= }.x01f(|x|)|xLi1

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ć.CDCDDCCfCfC


8

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=LNC


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.TPmPPNPNPP

Twierdzenie 1. Jeśli B jest obliczamy a nie w to istnieje obliczalną A tak, że P , P m B i B P T .PAAPAmPBBTPA

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 .CmCTCPC

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 .CmCTCPC

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


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
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 C = A C 0 (wersja jednolita), co odpowiadałoby na komentarz Michaëla Cadilhaca pod postem. C=NCC=AC0
Kaveh

5

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

NPP

AipBi1pB

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


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,


3
CBPPMANC

tak, wyliczenie maszyn z klas semantycznych nie jest rekurencyjne. Ale obiecujące wersje klas semantyki (promiseBPP, promiseMA, ...) są rzeczywiście sintaktyczne.
Marcos Villagra,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.