Klasy złożoności III-opracowanie

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 moga˛ byc´ wielomianowo zredukowane do problemu A ka˙zdy problem NPC mo˙ze by´c wielomianowo zredukowany do innego problemu NPC dla problemów klasy NPC znane sa˛ deterministyczne rozwia˛zania wykładnicze, nie wiadomo jednak, czy istnieja˛ inne, lepsze rozwia˛zania znalezienie rozwia˛zania wielomianowego dla jakiegokolwiek problemu NPC oznaczałoby, z˙e wszystkie problemy NPC posiadaja˛ równiez˙ rozwia˛zanie wielomianowe ... zobacz całą notatkę