Comment un problème peut-il être en NP, être NP-dur et non NP-complet?

Pendant longtemps, j'ai pensé qu'un problème était NP-complet s'il était à la fois (1) NP-dur et (2) en NP.

Cependant, dans le célèbre article "La méthode ellipsoïde et ses conséquences dans l'optimisation combinatoire" , les auteurs affirment que le problème du nombre chromatique fractionnaire appartient à NP et est NP-difficile, mais n'est pas connu pour être NP-complet. Sur la troisième page de l'article, les auteurs écrivent:

... nous notons que le problème de sommation d'un graphe est dans un sens équivalent au problème du nombre chromatique fractionnaire, et commentons le phénomène selon lequel ce dernier problème est un exemple de problème dans qui est N P -hard mais (comme pour l'instant) pas connu pour être N P- complet.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Comment est-ce possible? Me manque-t-il un détail subtil dans la définition de NP-complet?

Il semble que le problème soit le type de réductions utilisées pour chacun d'eux, et ils en utilisent différentes: ils signifient probablement " réductions réduites de Cook" et " N P- réductions complètes de Karp".$\mathsf{NP}$$\mathsf{NP}$

Parfois, les gens utilisent la version de réduction Cook de dureté car elle est applicable à des problèmes de calcul plus généraux (pas seulement des problèmes de décision). Bien que la définition originale de la dureté N P et de la complétude N P ait utilisé des réductions de Cook (réductions de Turing en temps polynomial), il est devenu rare d'utiliser des réductions de Cook pour la complétude N P (sauf indication contraire explicite). Je ne me souviens d'aucun article récent qui a utilisé N P -complete pour signifier N P -complete par rapport aux réductions Cook. (En note, le premier problème à prouver à N $\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$-hard était TAUT pas SAT et l'exhaustivité de SAT est implicite dans cette preuve.)

Maintenant, si vous regardez la section 7 du document, au bas de la page 195, vous verrez qu'ils signifient des réductions de dureté dureté.$\mathsf{NP}$

Donc, ce qu'ils signifient ici, c'est que le problème est dans , est difficile pour les réductions de N P wrt Cook, mais il n'est pas connu qu'il soit difficile pour les réductions de N P wrt Karp (réductions de plusieurs un en temps polynomial).$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$