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

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. $\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$

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 ?$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP\text{-}complete}$$\mathsf{NP\text{-}complete}$$\mathsf{NP}$$\mathsf{NP\text{-}complete}$

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$\emptyset$$\Sigma^*$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$$\mathsf{NP}$ .$\mathsf{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 .$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP\text{-}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 .$\mathsf{NP\text{-}complete}$$\mathsf{NP\text{-}complete}$

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 hierarchia$P \neq NP$$P$$NPC$$NP$$NPI$problemó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 $P \neq NP$$NPI$$P \neq NP$$NPI$$NP$$NPC$$P$; 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.

$BQP$$BQP$$NPC \not\subseteq BQP$$NPI$$BQP$

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 P ≠ NP . 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!

$P$

$P$$P$

$P$

¹ Podobny problem: izomorfizm pod wykresem jest NP-Complete w pełnym tego słowa znaczeniu.