Existe-t-il des problèmes «NP-intermédiaire-complet»?

Supposons P NP. $\ne$

Le théorème de Ladner dit qu'il existe des problèmes NP intermédiaires (problèmes dans NP qui ne sont ni dans P ni NP-Complete). J'ai trouvé en ligne des références voilées qui suggèrent (je pense) qu'il existe de nombreux "niveaux" de langues mutuellement réductibles au sein de NPI qui ne se résument certainement pas tous en un seul.

J'ai quelques questions sur la structure de ces niveaux.

Existe-t-il des problèmes "NP-Intermédiaire-Complet" - c'est-à-dire des problèmes NP-Intermédiaires auxquels tous les autres problèmes NP-Intermédiaires sont réductibles par le polytime?
Triez NP - P en classes d'équivalence, où la réductibilité mutuelle est la relation d'équivalence. Maintenant, imposez un ordre à ces classes d'équivalence: si les problèmes de réduisent à des problèmes de (il est donc clair que la classe d'équivalence NP-Complete est l'élément maximal). S'agit-il d'un ordre total (c'est-à-dire que les problèmes sont disposés dans une chaîne descendante infinie)? Sinon, la "structure arborescente" de l'ordre partiel a-t-elle un facteur de branchement fini? $A > B$ $B$ $A$
Existe-t-il d'autres composants structurels connus intéressants de NP-P? Y a-t-il des questions ouvertes intéressantes sur la structure sous-jacente?

Si l'un de ces éléments est actuellement inconnu, je serais intéressé de l'entendre également.

Merci!

cc.complexity-theory np np-intermediate GMB
la source

Une version faible de ceci est qu'il existe des problèmes "Graph-Isomorphism-Complete".

Suresh Venkat

π

$\pi$

π

$\pi$

N P

$\mathsf{NP}$

N P

$\mathsf{NP}$

P = N P

$\mathsf P=\mathsf{NP}$

Merci, Bruno - ces informations peuvent-elles toutes être trouvées dans l'article original de Ladner, ou devrait-il y avoir d'autres sources pertinentes?

GMB

Vous pouvez également consulter le document de Downey et Fortnow: Uniformly Hard Languages ; dans lequel la preuve du théorème de Ladner donnée à l'annexe A.1 montre que les degrés de temps polynomiaux des langues calculables sont un ordre partiel dense. Ils supposent également que s'il existe des ensembles uniformément durs dans NP, alors il existe des ensembles uniformément durs incomplets.

Marzio De Biasi

pour une autre référence pour 1. et une ressource peut-être utile, voir la réponse de Ryan et l'article de Schoening qui y est cité.

Sasho Nikolov

Je n'ai pas vraiment de références pour ces résultats - ils ne sont pas difficiles à prouver une fois que vous comprenez le théorème de Ladner.

Non, pour tout ensemble A incomplet NP, il existe un autre ensemble B strictement entre A et SAT.
Ces classes d'équivalence sont connues sous le nom de degrés polynomiaux-plusieurs-un. Vous pouvez intégrer n'importe quel poset fini dans les degrés en dessous de NP. En particulier, les degrés ne sont pas totalement ordonnés ou finement ramifiés.
Tout dépend de ce que vous entendez par «intéressant». Il existe une énorme théorie de la structure des degrés des ensembles calculables (voir le livre de Soare par exemple) et bon nombre de ces questions n'ont pas été portées vers les ensembles à temps polynomial. Par exemple, pouvez-vous avoir des ensembles NP A et B dont la jointure est équivalente à SAT et dont la rencontre est équivalente à l'ensemble vide?

Lance Fortnow
la source

A

$A$

B

$B$

C

$C$

(x, y) \in C

$(x,y) \in C$

x \in A

$x \in A$

y \in B

$y \in B$

Ce sont des termes de la théorie du réseau : la jointure d'un sous-ensemble est sa plus petite borne supérieure (si elle existe) et la rencontre la plus grande borne inférieure.

Bruno

Existe-t-il des problèmes «NP-intermédiaire-complet»?

Réponses: