Klasy złożoności IV-opracowanie

Nasza ocena:

3
Wyświetleń: 518
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Klasy złożoności IV-opracowanie - strona 1

Fragment notatki:

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ę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz