Klasa Co-NPC

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Problemy Co-NP-zupełne to takie problemy klasy Co-NP, że każdy inny problem klasy Co-NP może zostać do nich zredukowany, analogicznie jak dla problemów NP-zupełnych. Ponadto problem dopełniający względem problemu NP-zupełnego jest NP-trudny.