Czy występują problemy z „NP-Intermediate-Complete”?

13

Załóżmy, że P NP.

Twierdzenie Ladnera mówi, że istnieją problemy pośrednie NP (problemy w NP, które nie są ani w P, ani w NP-Complete). Znalazłem w Internecie kilka zawoalowanych odniesień, które sugerują (myślę), że istnieje wiele „poziomów” wzajemnie redukowalnych języków w ramach NPI, które zdecydowanie nie wszystkie się zlewają.

Mam pytania dotyczące struktury tych poziomów.

  1. Czy występują problemy „NP-Intermediate-Complete” - to znaczy problemy NP-Intermediate, do których każdy inny problem NP-Intermediate można zredukować w czasie polimerazy?
  2. Podziel NP - P na klasy równoważności, gdzie wzajemna redukowalność jest relacją równoważności. Teraz nałóż porządek na tych klasach równoważności: jeśli problemy w B zredukują się do problemów w A (więc wyraźnie klasa równoważności NP-Complete jest elementem maksymalnym). Czy jest to całkowite uporządkowanie (tzn. Problemy są ułożone w nieskończony malejący łańcuch)? Jeśli nie, to czy „struktura drzewa” częściowego uporządkowania ma skończony współczynnik rozgałęzienia?A>BBA
  3. Czy są jakieś inne interesujące znane elementy konstrukcyjne NP - P? Czy są jakieś interesujące otwarte pytania dotyczące podstawowej struktury?

Jeśli którekolwiek z nich są obecnie nieznane, chciałbym również to usłyszeć.

Dzięki!

GMB
źródło
3
Słaba wersja tego jest taka, że ​​występują problemy z „kompletnym izomorfizmem grafów”.
Suresh Venkat
7
ππNPNPP=NP
Dzięki, Bruno - czy wszystkie te informacje można znaleźć w oryginalnym artykule Ladnera, czy też powinny istnieć inne odpowiednie źródła?
GMB
Możesz także zajrzeć do dokumentu Downey i Fortnow: Uniformly Hard Languages ; w którym dowód twierdzenia Ladnera podany w dodatku A.1 pokazuje, że wielomianowe stopnie czasowe języków obliczeniowych są gęstym częściowym uporządkowaniem. Przypuszczają także, że jeśli w NP istnieją jednakowo twarde zbiory, to istnieją niekompletne i jednolicie twarde zbiory.
Marzio De Biasi
1
po kolejne odniesienie do 1. i potencjalnie użyteczne źródło, patrz odpowiedź Ryana i cytowany w niej artykuł Schoeninga.
Sasho Nikolov

Odpowiedzi:

31

Tak naprawdę nie mam referencji do tych wyników - nietrudno je udowodnić, gdy zrozumiesz twierdzenie Ladnera.

  1. Nie, dla każdego niekompletnego zestawu A A istnieje inny zestaw B ściśle między A i SAT.

  2. Te klasy równoważności są znane jako stopnie wielomianowe-wiele-jeden. Możesz osadzić dowolny skończony zbiór w stopniach poniżej NP. W szczególności stopnie nie są całkowicie uporządkowane lub nie mają końca.

  3. Wszystko zależy od tego, co rozumiesz przez „interesujące”. Istnieje ogromna teoria struktury stopni zestawów obliczalnych (patrz na przykład książka Soare'a) i wiele z tych pytań nie zostało przeniesionych do zbiorów wielomianowych. Na przykład, czy możesz mieć zestawy NP A i B, których łączenie jest równoważne SAT, a którego spotkanie jest równoważne pustemu zestawowi?

Lance Fortnow
źródło
1
ABC(x,y)CxAyB
8
Są to pojęcia teorii sieci : połączenie podzbioru jest jego najmniejszą górną granicą (jeśli istnieje) i spełnia najwyższą dolną granicę.
Bruno