Czy występują problemy z NP, nie w P i nie w NP Complete?

34

Czy są jakieś znane problemy w (a nie w ), które nie są ukończone? Rozumiem, że nie ma obecnie znanych problemów, ale nie zostało to wykluczone. NPPNP

Jeśli występuje problem, który to (a nie ), ale nie , czy byłby to wynik braku istniejącego izomorfizmu między instancjami tego problemu zestaw? Jeśli tak, to skąd wiemy, że problem nie jest „trudniejszy” niż to, co obecnie określamy jako zestaw ?NPPNP-completeNP-completeNPNP-complete

vpiTriumph
źródło
1
Zobacz także to powiązane pytanie .
Raphael

Odpowiedzi:

25

Czy są jakieś znane problemy w NP (a nie w P), które nie są NP Complete? Rozumiem, że nie ma obecnie znanych problemów, ale nie zostało to wykluczone.

Nie, nie jest to nieznane (z wyjątkiem trywialnych języków i , te dwa nie są kompletne z powodu definicji redukcji wielokrotnych jeden, zwykle te dwie są ignorowane przy rozważaniu redukcji wielokrotnych jeden). Istnienie problem, który jest niekompletna wrt wielomiejscowe jeden wielomian zmniejszyć czas Oznaczałoby to, że , które nie są znane (chociaż powszechnie uważa) . Jeśli dwie klasy są różne, to wiemy, że w występują problemy, które nie są kompletne, weź dowolny problem wΣNPNPPNPNP .P

Jeśli występuje problem, który jest NP (a nie P), ale nie NP Complete, czy byłby to wynik braku istniejącego izomorfizmu między wystąpieniami tego problemu a zestawem NP Complete?

Jeżeli dwie grupy złożoność różnią następnie twierdzenia Ladner występują problemy, które są -intermediate, czyli są one między P a N P - c o m s l e t e .NPPNP-complete

Jeśli tak, to skąd wiemy, że problem NP nie jest „trudniejszy” niż to, co obecnie określamy jako kompletny NP?

Nadal są wielomianowe, które można sprowadzać do problemów , więc nie mogą być trudniejsze niż problemy N P - c o m p l e t e .NP-completeNP-complete

Kaveh
źródło
Minęło kilka lat, ale miałem wrażenie, że problemy NP-Hard pasują do opisu OP, gdzie się mieszczą?
Kevin
2
@Kevin: Nie, NP-trudny oznacza, że ​​problem jest co najmniej tak trudny jak najtrudniejsze problemy w NP.
Huck Bennett
Co z problemami z czasem działania psuedo-wielomianu?
Joe
@Joe, nie jestem pewien, co masz na myśli, jeśli masz pytanie zadaj je jako nowe pytanie.
Kaveh
1
Och, oczywiście przy założeniu P! = NP. Takim problemem byłby izomorfizm grafów, prawda?
levi
11

Jak stwierdził @Kaveh, to pytanie jest interesujące tylko wtedy, gdy założymy ; reszta mojej odpowiedzi przyjmuje to jako założenie i przede wszystkim zawiera linki do dalszego osłabienia apetytu. Zgodnie z tym założeniem, według twierdzenia LADNER za wiemy, że istnieją problemy, które nie są ani w P ani N P C ; Problemy te są nazywane N P -intermediate lub N P ja . Co ciekawe, twierdzenie Ladnera można uogólnić na wiele innych klas złożoności, aby uzyskać podobne problemy pośrednie. Co więcej, twierdzenie to sugeruje również, że istnieje nieskończona hierarchiaPNPPNPCNPNPIproblemów pośrednich, które nie są poli czasie sprowadza się do siebie .NPI

Niestety, nawet przy założeniu bardzo trudno jest znaleźć problemy naturalne, które byłyby możliwe do udowodnienia N P I (oczywiście, że masz sztuczne problemy wynikające z dowodu twierdzenia Ladnera). Tak więc, nawet zakładając, że P N P w tym czasie, możemy jedynie wierzyć, że niektóre problemy są N P I, ale nie możemy tego udowodnić. Do takich przekonań dochodzimy, gdy mamy uzasadnione dowody, by sądzić, że problem N P nie występuje w N P C i / lub nie w PPNPNPIPNPNPINPNPCP; lub po prostu, gdy był badany przez długi czas i unikał dopasowania do jednej z klas. W tej odpowiedzi znajduje się dość wyczerpująca lista takich problemów . Obejmuje takie ulubione elementy jak faktoring, dyskretny dziennik i izomorfizm grafów.

BQPBQPNPCBQPNPIBQP

Artem Kaznatcheev
źródło
Naprawdę niedawny wynik Babai (patrz jeremykun.com/2015/11/12/… ) podaje quasipolynomalny algorytm dla izomorfizmu grafów, w zasadzie usuwając go z NPI, jeśli wynik się utrzymuje. Co ciekawe, problem ten nie był znany w BQP
Frédéric Grosshans,
1
@ FrédéricGrosshans posiadający quasipolynomialny algorytm czasu nie usuwa cię z NPI (w rzeczywistości nie usunąłby cię nawet z NPC, chyba że przyjmujesz silniejsze założenia niż tylko P! = NP). Wynik Babai (jeśli jest poprawny, co prawdopodobnie jest), dostarcza jedynie poszlakowych dowodów na to, że GraphIso może być w P, ponieważ w przeszłości, gdy znaleziono algorytmy quasipolynomialne dla trudnych problemów, ostatecznie doprowadziły one do algorytmów wielomianowych.
Artem Kaznatcheev,
1
@ FrédéricGrosshans Babai wycofał roszczenie dotyczące quasipolynomial runtime . Najwyraźniej wystąpił błąd w analizie.
Raphael
@Raphael, na podstawie mojego wcześniejszego komentarza, nie sądzę, aby Babai rozluźniający quasipolomomial do subexponential nie był szczególnie istotny w omawianej dyskusji.
Artem Kaznatcheev
Ponieważ ten komentarz wciąż tu jest, nie chciałem, żeby stał bez poprawek. (Zasadniczo wyśledziłem wszystkie wystąpienia „Babai” na stronie i opublikowałem ten sam komentarz.) Zachęcamy do oflagowania wszystkich komentarzy, które uznają za przestarzałe.
Raphael
7

Nie NP są znane problemy -Complete być w P . Jeśli istnieje algorytm czasu wielomianowego dla dowolnego problemu pełnego NP , to P = NP , ponieważ każdy problem w NP ma redukcję czasu wielomianowego do każdego problemu pełnego NP . (Tak właśnie definiuje się „ NP-zupełny ”.) I oczywiście, jeśli każdy problem z NP zakończony jest poza P , oznacza to, że PNP . Nie jesteśmy do końca pewni, dlaczego tak trudno jest to pokazać w ten czy inny sposób; gdybyśmy znali odpowiedź na to pytanie, prawdopodobnie wiedzielibyśmy znacznie więcej o P iNP . Mamy kilka technik dowodzenia, o których wiemy, że nie działają (na przykład relatywizacja i dowody naturalne), ale nie mamy podstawowego wyjaśnienia, dlaczego ten problem jest trudny.

Jeśli występują problemy w NP, które nie są w P , to w rzeczywistości istnieje nieskończona hierarchia problemów w NP między tymi w P i tymi, które są NP kompletne: jest to wynik zwany twierdzeniem Ladnera .

Mam nadzieję że to pomoże!

templatetypedef
źródło
proszę wyjaśnić: Nie wiadomo, że problemy w NP nie występują w P? Czy wszystkie P nie są już w NP?
1
@ Shimano- Są to dwie różne koncepcje: wszystkie problemy w P są znane z NP. Jednak nie wiemy, czy jakieś problemy w NP nie występują w P. Oznacza to, że P jest podzbiorem NP, ale nie wiemy, czy NP jest podzbiorem P. Czy to wyjaśnia rzeczy?
templatetypedef
Teraz sprawy stają się coraz wyraźniejsze. Dziękuję bardzo za szybkie odpowiedzi. Potrzebne jest jeszcze jedno wyjaśnienie. Powiedziałeś: „Powodem tego jest to, że każdy problem w NP ma redukcję czasu wielomianowego do każdego problemu kompletnego NP”. To dowodzi, że wszystkie problemy w NP są automatycznie uzupełniane NP? Znowu jestem trochę zdezorientowany
@ Shimano- Niezupełnie. Ważny jest kierunek redukcji. Problem jest NP-kompletny, jeśli wszystkie problemy w NP zredukują się do tego problemu. Można również wykazać, że problem jest trudny do przeprowadzenia przez NP, redukując znany problem NP-zupełny do tego problemu. Jednak pokazanie, że problem w NP sprowadza się do znanego problemu NP-zupełnego, nie pokazuje niczego nowego, ponieważ z definicji wszystkie problemy NP redukują się do wszystkich problemów NP-zupełnych.
templatetypedef
1
@ Twierdzenie Shimano-Ladnera mówi, że jeśli P! = NP, to muszą występować problemy NP-pośrednie, więc jeśli nie ma problemów NP-pośrednich, to P = NP. I tak - jeśli możemy znaleźć problem w NP, który nie jest w P, niezależnie od tego, czy jest w BQP, wtedy P! = NP.
templatetypedef