Pourquoi les problèmes NPI ne sont-ils pas tous de la même complexité?

Comment peut-on considérer un problème et pourquoi il est probable NP-intermédiaire par opposition à NP-complet? Il est souvent assez simple d'examiner un problème et de dire s'il est probablement NP-complet ou non, mais il me semble beaucoup plus difficile de dire si un problème est NP-intermédiaire car la ligne semble assez mince entre les deux. Des classes. Fondamentalement, ce que je demande, c'est pourquoi un problème qui peut être vérifié en temps polynomial (le cas échéant) mais non résolu en temps polynomial (tant que P n'est pas égal à NP) ne serait pas un temps polynomial réductible les uns aux autres. De plus, existe-t-il un moyen de montrer qu'un problème NP-Intermédiaire est similaire à la façon dont un problème est montré comme NP-Difficile, comme une réduction ou une autre technique? Tous les liens ou manuels qui pourraient m'aider à comprendre la classe de NP-intermédiaire seraient également appréciés.

cc.complexity-theory complexity-classes np-intermediate Jesse Stern
la source

"un problème qui peut être satisfait en temps polynomial", je suppose que vous voulez dire "un problème qui peut être vérifié en temps polynomial".

Kaveh

Il existe une classe de problèmes GI-complets qui sont polynomialement équivalents à l'isomorphisme graphique. L'IG est un problème majeur supposé être NP-intermédiaire

Mohammad Al-Turkistany

Au fait, le titre est trompeur, l'égalité de deux problèmes de complexité par rapport à une réduction (par exemple les réductions de Karp) est déjà définie, je vous suggère de le remplacer par quelque chose comme "Pourquoi les problèmes NPI ne sont pas tous de la même complexité?".

Kaveh

@kaveh A effectué toutes les modifications. Merci pour une autre excellente réponse!

Jesse Stern

"Il est souvent assez simple d'examiner un problème et de dire s'il est probable NP-Complete ou non". À mon humble avis, cela ne pouvait pas être plus éloigné de la vérité!

Mahdi Cheraghchi

Réponses:

Vous ne pouvez pas montrer qu'un problème est sans séparer de . $\mathsf{NPI}$ $\mathsf{P}$ $\mathsf{NP}$

Il y a des problèmes artificiels qui peuvent être prouvées pour être en en utilisant des généralisations du théorème de Lander (voir aussi ce ) en supposant que . $\mathsf{NPI}$ $\mathsf{NP}\neq\mathsf{P}$

Aussi la version rembourrée de problèmes sont $\mathsf{NEXP\text{-}complete}$ $\mathsf{NPI}$ en supposant que (voir aussi ce et ce ). $\mathsf{NEXP} \neq \mathsf{EXP}$

Un problème dans est souvent supposé être lorsque: $\mathsf{NP}$ $\mathsf{NPI}$

nous pouvons montrer sous des hypothèses raisonnables que ce n'est pas mais il n'est pas connu pour être en , $\mathsf{NPC}$ $\mathsf{P}$
nous pouvons montrer sous des hypothèses raisonnables qu'il n'est pas dans mais il n'est pas connu pour être dans , $\mathsf{P}$ $\mathsf{NPC}$

et parfois juste au moment où nous ne pouvons pas montrer qu'il est en ou . $\mathsf{NPC}$ $\mathsf{P}$

L' hypothèse de temps exponentiel (ou certaines autres hypothèses de dureté de calcul ) est un exemple d'hypothèse raisonnable .

Fondamentalement, ce que je demande, c'est pourquoi un problème qui peut être satisfait en temps polynomial (le cas échéant) mais non résolu en temps polynomial (tant que P n'est pas égal à NP) ne serait pas un temps polynomial réductible les uns aux autres.

$\mathsf{NPC}\not \subseteq \mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{NP}$

Kaveh
la source

"2. nous pouvons montrer sous des hypothèses raisonnables qu'il n'est pas dans P mais qu'il n'est pas connu pour être dans NP" Vous ne voulez pas dire "... dans NPC"?

Tyson Williams

@Victor, non, on ne sait pas que n'est pas égal à , et ils sont différents si et sont différents. Annulation de votre modification.

P

$\mathsf{P}$

N P C

$\mathsf{NPC}$

P

$\mathsf{P}$

N P

$\mathsf{NP}$

Kaveh

@Kaveh, je pense qu'il pensait aux langages triviaux ( et ), mais vous les excluez de P.

\emptyset

$\emptyset$

{0, 1}^{*}

$\{0,1\}^*$

didest

@Diego, eh bien, rien ne leur est réductible, mais vous avez raison. Je le réparerai.

Kaveh

@Kaveh et Diego: Oui, je pensais à ces langues triviales.

Victor Stafusa

Un cas typique est lorsqu'un problème dans réside également dans ou . En supposant que la hiérarchie polynomiale ne s'effondre pas, un tel problème ne peut pas être complet. Les exemples incluent la factorisation entière, le logarithme discret, l'isomorphisme du graphe, certains problèmes de réseau, etc. $\mathsf{NP}$ $\mathsf{coNP}$ $\mathsf{coAM}$ $\mathsf{NP}$

Mahdi Cheraghchi
la source

Un autre cas typique de problème est quand il y a un témoin de longueur mais plus petit que . Le problème de l'existence d'une clique de taille dans un graphe est un exemple typique - dans ce cas, le témoin (la clique spécifique) nécessite bits. $NPI$ $\omega(\log n)$ $n^{O(1)}$ $\log n$ $O(\log^2 n)$

En supposant l'hypothèse de temps exponentielle, un tel problème est plus facile qu'un problème complet (qui nécessite un temps ) mais plus difficile qu'un problème de temps polynomial. $NP$ $\exp(n^{O(1)})$

David Harris
la source