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 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

©operacji.org 2017
wyślij wiadomość