Czy znane są problemy NP-zupełne, ani trudne NP w silnym znaczeniu, ani algorytm pseudopolinomalny?

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.

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 ₁ ,…, a _m i k liczby całkowite b ₁ ,…, b _k ∈ {0,1}.
Pytanie : Czy oba poniższe mają zastosowanie?
(1) m całkowitymi ₁ , ..., _m tworzą tak- wystąpienie problem podziału. (2) k -bitowy ciąg b ₁ ... 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.

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.