Hierarchie w NP (przy założeniu, że P! = NP)

Zakładając, że P! = NP, uważam, że wykazano, że istnieją problemy, których nie ma w P, a nie w NP-Complete. Przypuszcza się, że takim problemem jest izomorfizm grafów.

Czy są jakieś dowody na istnienie większej liczby takich „warstw” w NP? tzn. Hierarchia złożona z więcej niż trzech klas, rozpoczynająca się od P i kończąca się NP, tak że każda z nich jest właściwym nadzbiorem drugiej?

Czy to możliwe, że hierarchia jest nieskończona?

Tak! W rzeczywistości istnieje pewna nieskończona hierarchia coraz trudniejszych problemów między P i NP-zupełnym przy założeniu, że P! = NP. Jest to bezpośrednia konsekwencja dowodu Twierdzenia Ladnera (który wykazał niepustość NP \ P)

Formalnie wiemy, że dla każdego zestawu S nie w P istnieje S 'nie w P, tak że S' jest redukowalne przez Karp do S, ale S nie jest redukowalne przez Cooka do S '. W związku z tym, jeśli p! = NP to istnieje nieskończona sekwencji S zestawów ₁ , S ₂ ... \ P NP w taki sposób, S _{i + 1} jest Karp, sprowadza się do S _i a S _i nie jest Stoły zredukować do S _{i + 1} .

Trzeba przyznać, że przeważająca większość takich problemów ma bardzo nienaturalny charakter.

Istnieje pojęcie „ograniczonego niedeterminizmu”, które ogranicza niedeterministyczne bity wymagane przez maszynę Turinga do znalezienia rozwiązania. Klasa NP wymaga na przykład bitów O (n). Ograniczając niedeterministyczne bity do polilogu, definiuje nieskończoną hierarchię klas złożoności zwaną hierarchią \ beta P, z których wszystkie mają własne problemy.

Zobacz na przykład następujący artykuł: Goldsmith, Levy, Mundhenk, „Limited nondeterminism”, SIGACT News, tom 27 (2), strony 20-29, 1996.