Klasy złożoności IV-opracowanie

Klasy złożoności IV problem decyzyjny A 2 NP nale˙zy do klasy NPH ( NP-Hard ), je˙zeli istnieje dla niego redukcja wielomianowa do problemów NPC . nie wiadomo jak przekształci´c problem NPC do problemu NPH klasa co Ü NP to klasa problemów, które sa˛ dopełnieniami problemów z klasy NP. W szczególnos´ci wszystkie problemy klasy P sa˛ NP , poniewaz˙ moz˙na je sprawdzi´c w czasie wielomianowym ( P _ NP ). Nie ma dowodu na to, czy istnieje problem P , który nie jest w klasie NP ( P 6 = NP lub P _ NP ) ... zobacz całą notatkę