Jak problem może występować w NP, być trudnym NP, a nie kompletnym NP?

Najdłużej myślałem, że problem był NP-zupełny, jeśli jest zarówno (1) NP-trudny, jak i (2) jest w NP.

Jednak w słynnym artykule „Metoda elipsoidy i jej konsekwencje w optymalizacji kombinatorycznej” autorzy twierdzą, że problem ułamkowej liczby chromatycznej należy do NP i jest trudny do NP, ale nie jest znany jako NP-zupełny. Na trzeciej stronie artykułu autorzy piszą:

... możemy zauważyć, że problem pakowania wierzchołek grafu jest w sensie odpowiednik frakcyjnej chromatycznej Problem numer i komentarz na temat tego zjawiska, że ten ostatni problem jest przykładem problemu w , który jest N P -hard a (jak do tej pory), nie wiadomo, że N P -Complete.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Jak to jest możliwe? Czy brakuje mi subtelnego szczegółu w definicji NP-complete?

Wygląda na to, że problemem jest rodzaj redukcji zastosowanej dla każdego z nich, i używają one innych: prawdopodobnie oznaczają one „ twarde wrt Redukcje Cooka” i „ N P- całkowite redukcje wrt Karp”.$\mathsf{NP}$$\mathsf{NP}$

Czasami ludzie używają wersji twardości redukcją Cooka, ponieważ ma ona zastosowanie do bardziej ogólnych problemów obliczeniowych (nie tylko problemów decyzyjnych). Chociaż oryginalny definicja zarówno N P -hardness i N P o używanych redukcje Cooka -completeness (wielomian czasie Turinga redukcje) stało się rzadkością, aby korzystać redukcje gotować N P -completeness (o ile nie wskazano wyraźnie). Nie przypominam sobie każdy ostatni papier, który został użyty N P -Complete oznaczać N P -Complete WRT redukcje gotować. (Jako marginesie pierwszy problem, który okazał się być N $\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$- twarde było TAUT nie SAT, a kompletność SAT jest domniemana w tym dowodzie.)

Teraz, jeśli spojrzysz na sekcję 7 artykułu, na dole strony 195, zobaczysz, że oznaczają one twardość w stosunku do redukcji Turinga.$\mathsf{NP}$

Więc co tu na myśli to, że problem jest w , jest trudne do N P wrt redukcji Cooka, ale nie wiadomo, aby być trudne dla N P wrt redukcje Karp (wielomian czasie wiele-jeden redukcje).$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$