Wypukłym, jeżeli dla każdych dwóch punktów punkt należy do dla każdego Def. 2 Hiperpłaszczyzną


Złożonością obliczeniową problemu



Pobieranie 2,11 Mb.
Strona12/22
Data24.02.2019
Rozmiar2,11 Mb.
1   ...   8   9   10   11   12   13   14   15   ...   22
Złożonością obliczeniową problemu nazywamy złożoność najlepszego możliwego algorytmu rozwiązującego ten problem
Def. 4.6 Klasą P nazywamy klasę problemów decyzyjnych, których złożoność obliczeniowa jest wielomianowa
Def. 4.7 Mówimy, że problem decyzyjny należy do klasy NP, jeśli istnieje wielomian p(n) zależny od rozmiaru tego problemu oraz algorytm  (algorytm weryfikacji potwierdzenia) takie, że dla każdego konkretnego problemu z odpowiedzią „tak” i łańcucha danych x(z) istnieje łańcuch (potwierdzenie odpowiedzi „tak”) c(x) symboli alfabetu wyjściowego , dla którego:

- |c(x)|=



- algorytm  po otrzymaniu na wejściu sekwencji x(z) # c(x(z)) (# koniec danych, początek potwierdzania) dochodzi do odpowiedzi „tak” po nie więcej niż p(N(z)) krokach
Def. 4.8 Problem decyzyjny 1 jest wielomianowo transformowalny do 2, jeśli dla dowolnego łańcucha x danych problemu 1 można w wielomianowym czasie (wielomian zależy od |x(z)|) zbudować łańcuch y danych problemu 2, taki, że: x(z) będzie łańcuchem danych konkretnego problemu z odpowiedzią „tak” wtedy i tylko wtedy, gdy y(z’) będzie łańcuchem danych konkretnego problemu z odpowiedzią „tak”; oznaczmy to następująco:
Def. 4.9 Problem nazywamy


1   ...   8   9   10   11   12   13   14   15   ...   22


©operacji.org 2019
wyślij wiadomość

    Strona główna