Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona2/19
Data23.02.2018
Rozmiar1,74 Mb.
1   2   3   4   5   6   7   8   9   ...   19

Rozdział 1


Elementy teorii złożoności obliczeniowej


          1. Złożoność obliczeniowa algorytmów

Złożoność obliczeniową dowolnego algorytmu charakteryzują dwie funkcje: T(n) i S(n), gdzie argument n oznacza długość danych wejściowych - ilość bitów potrzebnych do ich zapisania (jeżeli x jest pewną daną, to jej długość oznaczamy |x|). T(n) określa złożoność czasową algorytmu (ilość wykonywanych operacji), natomiast S(n) złożoność przestrzenną (ilość potrzebnych do obliczeń komórek pamięci). Wielkości te mogą być wyrażane za pomocą następującej notacji „O”.


Definicja 1.1

Załóżmy, że dla wszystkich argumentów n większych od pewnego n0 funkcje f(n) i g(n) są określone, przyjmują wartości dodatnie i dla pewnej stałej cR zachodzi f(n)  cg(n). Wówczas oznaczamy f = O(g).


Dużą zaletą wyznaczania w ten sposób złożoności czasowej jest uniezależnienie wyniku od szybkości maszyny, na którym badany algorytm jest wykonywany. Dla algorytmów o dużej złożoności obliczeniowej (a takie występują w kryptografii) przestają być istotne parametry techniczne komputera. Wtedy ogromne znaczenie ma rząd wielkości złożoności obliczeniowej algorytmu.
Algorytmy można sklasyfikować w zależności od ich złożoności czasowej lub przestrzennej. Tabela 1.0 przedstawia kilka przykładowych klas algorytmów oraz dla porównania czasy obliczeń dla danych długości jednego miliona bitów, przy założeniu że jedna operacja wykonywana jest w 10–6 sekundy [6].
    1. Tabela 1.1


Klasa algorytmu

Złożoność

Liczba operacji

Czas wykonania

Stały

O(1)

1

1 mikrosekunda

Liniowy

O(n)

106

1 sekunda

Kwadratowy

O(n2)

1012

11,6 dnia

Sześcienny

O(n3)

1018

32000 lat

Wykładniczy

O(2n)

10301030

10301006  wiek istnienia Wszechświata

Uwaga: wiek istnienia wszechświata szacuje się na około 14 miliardów lat.
    1. Można zauważyć, że czas wykonania algorytmu o wykładniczej złożoności czasowej znacznie różni się od czasu wykonania pozostałych rodzajów algorytmów przedstawionych w tabeli 1.0. Dla algorytmu sześciennego oczekiwanie na wynik obliczeń przy długości danych wejściowych 106 bitów nie ma praktycznego sensu (choć hipotetycznie można założyć, że po upływie 32000 lat komputer przedstawi rozwiązanie). Dla algorytmu wykładniczego o takiej samej długości danych wejściowych oczekiwanie na rozwiązanie niezależnie od wszystkiego jest daremne.

    2. Wyróżnia się pewną klasę algorytmów, które mają duże znaczenie praktyczne. Są to algorytmy czasu wielomianowego.




    1. Definicja 1.2


Mówimy, że algorytm jest czasu wielomianowego, jeżeli istnieje stała całkowita d taka, że liczba operacji potrzebnych do jego wykonania na danych wejściowych o łącznej długości nie przekraczającej n jest rzędu O(nd).
Definicja 1.2 w niektórych przypadkach może okazać się myląca. Na przykład algorytm dla danych wejściowych długości n i złożoności czasowej n100 jest wolniejszy od algorytmu o złożoności czasowej e0.001n dla n mniejszego od około 107. Mimo to pierwszy algorytm jest algorytmem czasu wielomianowego, natomiast drugi ma złożoność wykładniczą. Doświadczenie jednak wskazuje, że jeżeli dla problemu o znaczeniu praktycznym istnieje algorytm rozwiązujący go w czasie wielomianowym, to stała d z definicji 1.2 nie jest duża.
Definicja 1.3

Problemem decyzyjnym nazywamy taki problem, którego wynik jest odpowiedzią „tak” lub „nie”. Jeżeli zaś rozwiązaniem problemu jest coś więcej (np. liczba), to problem taki nazywamy poszukiwawczym.


Problemy poszukiwawcze mogą mieć kilka poprawnych odpowiedzi natomiast problemy decyzyjne tylko jedną.
Przykład 1.1

Przypadek problemu decyzyjnego faktoryzacji liczb całkowitych.



Dane: x, yZ+

Pytanie: czy istnieje liczba całkowita z[2, y – 1] taka, że z|x ?

Odpowiedź: „tak” lub „nie”.
Przykład 1.2

Przypadek problemu poszukiwawczego faktoryzacji liczb całkowitych.



Dane: x, yZ+

Pytanie: czy istnieje liczba całkowita z[2, y – 1] taka, że z|x ?

Odpowiedź: z (jeżeli istnieje).
Dla wielu problemów odnośny problem decyzyjny i poszukiwawczy są równoważne (algorytm rozwiązujący jeden z nich można łatwo przekształcić tak, aby rozwiązywał drugi). Tak więc ograniczając się do problemów decyzyjnych zazwyczaj nie traci się ogólności.

          1. Klasy problemów P i NP

Dzięki teorii złożoności można klasyfikować problemy według algorytmów koniecznych do ich rozwiązania.



    1. Definicja 1.4


Problem decyzyjny należy do klasy P problemów rozwiązywalnych w czasie wielomianowym, jeżeli istnieje deterministyczny algorytm czasu wielomianowego rozwiązujący ten problem.

Definicja 1.5

Problem decyzyjny należy do klasy NP, jeżeli dla każdego przypadku tego problemu osoba dysponująca nieograniczoną mocą obliczeniową może odpowiedzieć poprawnie na pytanie będące treścią tego problemu oraz gdy odpowiedź brzmi „tak”, jest w stanie dostarczyć dowód, którego inna osoba może użyć do sprawdzenia poprawności odpowiedzi w czasie wielomianowym (dowód ten nazywamy certyfikatem).

Problem decyzyjny należy do klasy co-NP, jeżeli spełnia analogiczny warunek jak powyżej, w którym odpowiedź „tak” zastąpiona jest odpowiedzią „nie”.
Przytoczony wcześniej problem decyzyjny faktoryzacji liczb całkowitych należy do klasy NP. Osoba dysponująca nieograniczoną mocą obliczeniową rozkłada liczbę x na czynniki, znajduje czynnik z[2, y – 1] a następnie przekazuje drugiej osobie odpowiedź „tak” i liczbę z. Oczywiście ta druga osoba może sprawdzić w czasie wielomianowym (dzieląc x przez z) czy otrzymana odpowiedź jest poprawna.
Powyższy problem należy także do klasy co-NP. Jeśli odpowiedź brzmi „nie”, to osoba dysponująca nieograniczoną mocą obliczeniową podaje wraz z odpowiedzią rozkład x na czynniki pierwsze, z którego można odczytać, że nie ma czynnika niewiększego od y. Ponadto dostarcza certyfikaty pierwszości powyższych czynników pozwalające stwierdzić w czasie wielomianowym, że są one liczbami pierwszymi.
Ważnym zagadnieniem teorii złożoności obliczeniowej jest możliwość redukowania problemów.
Definicja 1.6

Niech A1 i A2 będą problemami decyzyjnymi. Mówimy, że A1 redukuje się w czasie wielomianowym do A2 jeżeli istnieje algorytm, którego czas działania jest wielomianowy ze względu na długość danych wejściowych problemu A1 i który dla każdego przypadku 1 problemu A1 konstruuje przypadek 2 problemu A2 taki, że 1 i 2 mają taką samą odpowiedź.


Załóżmy, że dysponujemy efektywnym algorytmem rozwiązującym problem A2. Jeżeli problem A1 redukuje się do A2, to można użyć algorytmu dla A­2 do rozwiązania A1. Niech dany będzie pewien przypadek problemu A1. Za pomocą odpowiedniego algorytmu (o którym mowa w definicji 1.6) można znaleźć w czasie wielomianowym odpowiadający mu przypadek problemu A­2. Odpowiedź, jaką daje algorytm dla A zastosowany do skonstruowanego przypadku jest odpowiedzią dla wyjściowego przypadku problemu A1. Jeżeli algorytm dla A2 był algorytmem czasu wielomianowego, to otrzymany algorytm dla A1 również jest algorytmem czasu wielomianowego.
Przykład 1.3

Problem A1:



Dane: wielomian p(x) stopnia drugiego o współczynnikach całkowitych.

Pytanie: czy p(x) ma dwa różne pierwiastki rzeczywiste?
Problem A2:

Dane: liczba całkowita n.

Pytanie: czy n jest liczbą dodatnią?
Problem A­1 redukuje się do A2.

Niech p(x) = ax2 + bx + c będzie przypadkiem problemu A­1. Wówczas n = b2 – 4ac można policzyć w czasie wielomianowym. Problem A2 z daną wejściową n ma odpowiedź pozytywną wtedy i tylko wtedy, gdy odpowiedź pozytywną ma problem A1 z daną wejściową ax2 + bx + c.


Jeżeli wszystkie problemy klasy NP są rozwiązywalne deterministycznie w czasie wielomianowym, to NP = P. Do tej pory nie zostało udowodnione czy NP = P lub czy NP  P. Jednak wszystko wskazuje na to, że klasy te nie są równe.
W klasie NP można wyróżnić grupę problemów o bardzo ważnej własności.
Definicja 1.7

Problem decyzyjny klasy NP nazywamy problemem NP-zupełnym, jeśli każdy inny problem klasy NP można do niego zredukować w czasie wielomianowym.



Okazuje się więc, że w klasie NP istnieją takie problemy, dla których można udowodnić, że są tak samo trudne, jak dowolny inny problem w tej klasie.
Znaleziono bardzo dużo problemów NP-zupełnych. Jednym z nich jest problem komiwojażera. Załóżmy, że wędrowny sprzedawca musi odwiedzić określoną liczbę miast przy jednoczesnym ograniczeniu maksymalnej odległości, jaką może przebyć. Czy istnieje taka droga, aby komiwojażer odwiedził każde miasto dokładnie jeden raz?
Jeżeli istniałby deterministyczny algorytm rozwiązujący problem komiwojażera w czasie wielomianowym, to musi zachodzić równość P = NP. Odwrotnie, jeżeli dla każdego problemu w klasie NP nie istnieje deterministyczny algorytm czasu wielomianowego, to również taki algorytm nie istnieje dla problemu komiwojażera.

          1. Problem łamania dla kryptosystemu z kluczem jawnym

Powróćmy teraz do kryptografii. Załóżmy, że naszym zadaniem jest poddanie kryptoanalizie systemu kryptograficznego z kluczem jawnym (tzw. problem łamania). Znamy więc pewien klucz publiczny E i funkcję różnowartościową fE: P→C, gdzie P jest zbiorem jednostek tekstu jawnego a C zbiorem szyfrogramów oraz dysponujemy przechwyconym szyfrogramem cC. Naszym zadaniem jest wyznaczenie takiego pP, że fE(p) = c. Problem łamania dla kryptosystemu z kluczem jawnym można przedstawić następująco:


Dane: E, fE: P→C, cC.

Wynik: pP takie, że fE(p) = c.
Jednak w tym przypadku wiemy jeszcze coś więcej: istnieje tylko jedno takie pP, że fE(p) = c. Stąd problem łamania jest trochę innego rodzaju.



1   2   3   4   5   6   7   8   9   ...   19


©operacji.org 2017
wyślij wiadomość

    Strona główna