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 187 Kb.
Strona12/22
Data24.02.2019
Rozmiar187 Kb.
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

Pobieranie 187 Kb.

Share with your friends:
1   ...   8   9   10   11   12   13   14   15   ...   22




©operacji.org 2020
wyślij wiadomość

    Strona główna
warunków zamówienia
istotnych warunków
przedmiotu zamówienia
wyboru operacji
Specyfikacja istotnych
produktu leczniczego
oceny operacji
rozwoju lokalnego
strategii rozwoju
kierowanego przez
specyfikacja istotnych
Nazwa przedmiotu
Karta oceny
ramach działania
przez społeczno
obszary wiejskie
dofinansowanie projektu
lokalnego kierowanego
Europa inwestująca
Regulamin organizacyjny
przetargu nieograniczonego
kryteria wyboru
Kryteria wyboru
Lokalne kryteria
Zapytanie ofertowe
Informacja prasowa
nazwa produktu
Program nauczania
Instrukcja obsługi
zamówienia publicznego
Komunikat prasowy
programu operacyjnego
udzielenie zamówienia
realizacji operacji
opieki zdrowotnej
przyznanie pomocy
ramach strategii
Karta kwalifikacyjna
oceny zgodno
Specyfikacja techniczna
Instrukcja wypełniania
Wymagania edukacyjne
Regulamin konkursu
lokalnych kryteriów
strategia rozwoju
sprawozdania finansowego
ramach programu
ramach poddziałania
kryteriów wyboru
operacji przez
trybie przetargu