Czy są jakieś NP całkowite problemy bez nieskończonego podzbioru instancji takie, że członkostwo w można ustalić w czasie wielomianowym, a dla wszystkich , można rozwiązać w czasie wielomianowym? (Zakładając )
Odpowiedzi:
Zobacz odpowiedź Josha Grochowa na nadzbiór czasu Poly pełnego języka NP z nieskończenie wieloma ciągami znaków wyłączonymi z niego . Zgodnie z tą odpowiedzią, przy pewnych naturalnych założeniach kryptograficznych, dla każdego problemu uzupełniającego NP występuje nieskończony podzbiór przypadków, w których członkostwo w Φ jest czasem wielomianowym, a problem decyzyjny ograniczony do Φ jest trywialny (odpowiedź zawsze nie) .
Można to sformalizować, stwierdzając, że żaden kompletny kompletny NP nie jest odporny na P. Wiadomo również (ponownie przy założeniach kryptograficznych), że żaden kompletny NP nie jest odporny na P. Więc nie ma innej nieskończony podzbiór takie, że członkostwo w cp ' jest sprawdzalne wielomian czasu i problem decyzja ogranicza się do cp ' ma zawsze Tak Answer. Patrz np. Glasser i in., „Właściwości kompletnych zestawów NP”, SICOMP 2006, doi: 10.1137 / S009753970444421X .
Pierwszą obserwacją jest to, że posiadanie dokładnie tego, o co prosisz, byłoby dowodem na to, że ponieważ oznaczałoby, że zbioru wszystkich instancji nie można rozwiązać w czasie wielomianowym.
Myślę jednak, że o to ci chodziło, możemy trochę pogodzić się z tym, co rozumiemy przez „rozwiązany w czasie wielomianowym”. Jeśli rozumiemy przez nią wszystkich nieskończonych podzbiorów wystąpień, których członkostwo w P są N P -Complete, to odpowiedź nie przez Mahaney Twierdzenie (jest http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute -to-mahaney.html ). Twierdzenie to stwierdza, że nie NP-zupełny problem może być rzadki chyba P = N P . Teraz, biorąc pod podzbiór instancji { 0 i ∣ i ∈ N } , mamy nieskończony rzadki podzbiór instancji, dla których testowane jest członkostwo , które nie mogą być N P -Complete chyba P = N P przez Mahaney Twierdzenie.