Klasy złożoności III-opracowanie

Nasza ocena:

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

Pobierz ten dokument za darmo

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

Fragment notatki:

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ę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz