69002

Klasy złożoności III

problem decyzyjny A 2 NP nale zy do klasy NPC (NP-Complete), jez eli wszystkie problemy z klasy NP mogą, byc' wielomianowo zredukowane do problemu A

ka zdy problem NPC mo zęby cwielomianowo zredukowany do innego problemu NPC

dla problemów klasy NPC znane sa, deterministyczne rozwia, zania wykładnicze, nie wiadomo jednak, czy istnieją, inne, lepsze rozwia, zama znalezienie rozwia, zania wielomianowego dla jakiegokolwiek problemu NPC oznaczałoby, ze wszystkie problemy NPC posiadaja, również rozwia, zanie wielomianowe