|
 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
|
| Strona | 12/22 | | Data | 24.02.2019 | | Rozmiar | 2,11 Mb. |
|
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
|
|
|
