W swoim artykule (s. 503) Garey i Johnson zauważają:
... może istnieć problem NP-zupełny, który nie jest ani NP-zupełny w sensie silnym, ani rozwiązany przez algorytm pseudo-wielomianowy ...
Czy ktoś zna problemy z kandydatami dotyczące wyżej wymienionych właściwości?
Myślę, że możliwą odpowiedzią na to pytanie może być lista problemów NP-zupełnych w zwykłym sensie, tak że nie jest dla nich znany żaden algorytm pseudopolinomialny.
ds.algorithms
np-hardness
np
Oleksandr Bondarenko
źródło
źródło
Odpowiedzi:
Nie wiem, czy chcesz dowiedzieć się więcej o moim komentarzu do twojego pytania, ale tutaj i tak jest więcej szczegółów.
Jeśli P = NP, każdy problem w NP można rozwiązać w czasie wielomianowym, a zatem w czasie pseudo-wielomianowym, co oznacza, że żaden problem nie spełnia twoich wymagań, jak zauważył Magnus w swojej odpowiedzi. Więc załóż P ≠ NP w pozostałej części tej odpowiedzi.
Ponieważ P ≠ NP istnieje język L ∈NP ∖ P, który nie jest NP-zupełny (twierdzenie Ladnera). Rozważ następujący problem:
Bezpośredni iloczyn partycji i
wystąpienia L : m dodatnie liczby całkowite a 1 ,…, a m i k liczby całkowite b 1 ,…, b k ∈ {0,1}.
Pytanie : Czy oba poniższe mają zastosowanie?
(1) m całkowitymi 1 , ..., m tworzą tak- wystąpienie problem podziału. (2) k -bitowy ciąg b 1 ... b k należy do L .
Zgodnie z opracowaniem Gareya i Johnsona zdefiniuj funkcję Długość jako m + ⌈log max i a i ⌉ + k, a funkcję Max jako max i a i .
Rutynowo sprawdza się (i), czy jest NP-zupełny w słabym znaczeniu, (ii) czy nie ma algorytmu pseudo-wielomianowego, oraz (iii), że nie jest NP-zupełny w silnym sens.
(Wskazówki: (i) Członkostwo w NP wynika z faktu, że zarówno problem z partycją, jak i L. są w NP. W przypadku twardości NP, zredukuj Partycjonowanie do tego problemu. (Ii) Skonstruuj pseudo-wielomianową transformację z L do tego problemu. (iii) Skonstruuj pseudo-wielomianową transformację z tego problemu do L , wykorzystując fakt, że partycja ma algorytm pseudo-wielomianowy.)
W tej konstrukcji nie ma nic szczególnego w problemie z partycją: możesz użyć swojego ulubionego słabego problemu NP-zupełnego z algorytmem pseudo-wielomianowym.
źródło
Powiedziałbym, że odpowiedź jest jednoznaczna „nie” (to znaczy nikt nie wie), ponieważ nikt nie wie, czy problemy NP-zupełne można rozwiązać w czasie wielomianowym , nie mówiąc już o czasie pseudo- wielomianowym. (Każdy algorytm wielomianowy jest oczywiście pseudopolimiczny.) Jeśli możesz znaleźć problem w NPC, którego nie można rozwiązać w czasie pseudopoliminalnym, właśnie udowodniłeś, że P ≠ NP, więc myślę, że bezpiecznie jest powiedzieć, że żadne takie przykłady nie będą wyprodukowane w najbliższym czasie.
źródło