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

14

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.NPNPNP

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

Austin Buchanan
źródło

Odpowiedzi:

27

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”.NPNP

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 PNPNPNPNPNPNPNP- 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.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).NPNPNP

Kaveh
źródło
1
Czy masz na myśli DNF-Tautology by Taut? Czy to nie jest kompletne CoNP? Ponieważ CNT-Tautologia jest trywialna.
Tayfun Pay
1
@TayfunPay: Najprawdopodobniej tautologia dla dowolnych formuł nie tylko CNF lub DNF. A Co-NP-complete i NP-complete to te same wrt Redukcje Cooka, dlatego Kaveh wspomina o tej anegdocie.
frafl
1
@Tayfun, Cook udowadnia to dla ogólnych wzorów i używa go DNF-TAUT jest następstwem tego artykułu. Oba są NP- hard wrt Redukcje Cooka.
Kaveh
@frafl, „NP-complete” jest zdefiniowany w artykule Karpa z 1972 roku . Papier Cooka z 1971 roku określa redukcje Cooka i udowadnia, że ​​TAUT jest trudny do NP. Dowodzi to również, że wiele problemów jest równoważnych z ograniczeniami Cooka. Kompetencja NP nie jest jednak wyraźnie stwierdzona w oryginalnym artykule.
Kaveh