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

Załóżmy, że P NP. $\ne$

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.

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?
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 zredukują się do problemów w (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 > B$ $B$ $A$
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!

cc.complexity-theory np np-intermediate GMB
źródło

Słaba wersja tego jest taka, że występują problemy z „kompletnym izomorfizmem grafów”.

Suresh Venkat

π

$\pi$

π

$\pi$

N P

$\mathsf{NP}$

N P

$\mathsf{NP}$

P = N P

$\mathsf P=\mathsf{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

po kolejne odniesienie do 1. i potencjalnie użyteczne źródło, patrz odpowiedź Ryana i cytowany w niej artykuł Schoeninga.

Sasho Nikolov

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

Nie, dla każdego niekompletnego zestawu A A istnieje inny zestaw B ściśle między A i SAT.
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.
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

A

$A$

B

$B$

C

$C$

(x, y) \in C

$(x,y) \in C$

x \in A

$x \in A$

y \in B

$y \in B$

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

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

Odpowiedzi: