Wie kann ein Problem in NP sein, NP-hart und nicht NP-vollständig?

Die längste Zeit habe ich gedacht, dass ein Problem NP-vollständig ist, wenn es sowohl (1) NP-schwer als auch (2) NP ist.

In der berühmten Veröffentlichung "Die Ellipsoidmethode und ihre Konsequenzen für die kombinatorische Optimierung" behaupten die Autoren jedoch, dass das Problem der fraktionalen chromatischen Zahl zu NP gehört und NP-hart ist, von dem jedoch nicht bekannt ist, dass es NP-vollständig ist. Auf der dritten Seite des Papiers schreiben die Autoren:

... Wir stellen fest, dass das Vertexpackungsproblem eines Graphen in gewissem Sinne dem fraktionalen Farbzahlproblem äquivalent ist, und kommentieren das Phänomen, dass dieses letztere Problem ein Beispiel für ein Problem in ist, das N $\mathsf{NP}$$\mathsf{NP}$ -hart ist aber (wie bisher) nicht als -vollständig bekannt.$\mathsf{NP}$

Wie ist das möglich? Fehlt mir ein subtiles Detail in der Definition von NP-complete?

Es scheint, dass das Problem die Art der für jeden von ihnen verwendeten Reduzierungen ist, und sie verwenden unterschiedliche: Sie bedeuten wahrscheinlich " hart für Cook-Reduzierungen" und " N $\mathsf{NP}$$\mathsf{NP}$ -vollständige für Karp-Reduktionen".

Manchmal wird die Cook-Reduktionsversion der -Härte verwendet, weil sie auf allgemeinere Rechenprobleme (nicht nur Entscheidungsprobleme) anwendbar ist. Obwohl in der ursprünglichen Definition sowohl der N P -Härte als auch der N P -Vollständigkeit Cook-Reduktionen (Polynomzeit-Turing-Reduktionen) verwendet wurden, ist es selten geworden, Cook-Reduktionen für die N P -Vollständigkeit zu verwenden (sofern nicht ausdrücklich angegeben). Ich erinnere mich an keine neuere Veröffentlichung, in der N P -komplett für N P -komplett für Cook-Reduktionen verwendet wurde. (Als Randbemerkung das erste Problem, das N nachgewiesen werden soll$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$-hard war TAUT nicht SAT und die Vollständigkeit für SAT ist in diesem Beweis enthalten.)

Wenn Sie sich jetzt Abschnitt 7 des Papiers unten auf Seite 195 ansehen, werden Sie sehen, dass sie N P bedeuten$\mathsf{NP}$ -Härte für Reduzierungen .

Was sie hier bedeuten, ist, dass das Problem in , ist schwer für N P bezogen auf Cook-Reduktionen, aber es ist unbekannt, dass es schwer für N P bezogen auf Karp-Reduktionen ist (polynomielle Viel-Eins-Reduktionen).$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$