Klasa Co-NP

Czytaj Dalej

Jakiego rodzaju problemy tworzą klasę problemów NP – zupełnych? Podaj przykłady

Klasę problemów NP – zupełnych tworzą problemy o następujących cechach: - każdy taki problem da się w czasie wielomianowym przekształcić do innego - dla wszystkich istnieją wątpliwe (wykładnicze) rozwiązania - dla żadnego nie znaleziono rozsądnego (wielomianowego) rozwiązania - dla żadnego nie udowodniono, że wymaga on czasu wykładniczego - wszystkie te problemy są ze sobą powiązane (jeśli dla choćby jednego uda się znaleźć wielomianowe ...