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.
Jak to jest możliwe? Czy brakuje mi subtelnego szczegółu w definicji NP-complete?
źródło