Hiérarchies dans NP (sous l'hypothèse que P! = NP)

En supposant que P! = NP, je crois qu'il a été démontré qu'il y a des problèmes qui ne sont pas en P et non NP-Complete. L'isomorphisme graphique est supposé être un tel problème.

Existe-t-il des preuves de plus de telles «couches» dans NP? c'est-à-dire une hiérarchie de plus de trois classes commençant par P et aboutissant à NP, de telle sorte que chacune est un surensemble approprié de l'autre?

Est-il possible que la hiérarchie soit infinie?

Oui! En fait, il existe une hiérarchie infinie de problèmes de plus en plus difficiles entre P et NP-complet sous l'hypothèse que P! = NP. Ceci est un corollaire direct de la preuve du théorème de Ladner (qui a établi la non-vacuité de NP \ P)

Formellement, nous savons que pour tout ensemble S qui n'est pas dans P, il existe S 'pas dans P tel que S' est Karp réductible à S mais S n'est pas Cook-réductible à S '. Par conséquent, si P! = NP, alors il existe une séquence infinie d'ensembles S ₁ , S ₂ ... dans NP \ P tels que S _{i + 1} est Karp-réductible à S _i mais S _i n'est pas Cook-réductible à S _{i + 1} .

Certes, la grande majorité de ces problèmes sont de nature très peu naturelle.

Il existe une notion de "non-déterminisme limité" qui limite les bits non déterministes requis par la machine de Turing pour arriver à une solution. La classe NP nécessite par exemple O (n) bits. En limitant les bits non déterministes au polylogue, on définit une hiérarchie infinie de classes de complexité appelée hiérarchie \ beta P, toutes avec leurs propres problèmes.

Voir, par exemple, l'article suivant pour plus de détails: Goldsmith, Levy, Mundhenk, "Limited nondeterminism", SIGACT News, vol 27 (2), pages 20-29, 1996.