Co to jest czas pseudo wielomianowy? Czym różni się od czasu wielomianowego?

Co to jest czas pseudo wielomianowy ? Czym różni się od czasu wielomianowego? Niektóre algorytmy działające w czasie pseudo wielomianowym mają czasy wykonania, takie jak O (nW) (dla problemu plecakowego 0/1 ) lub O (√n) (dla podziału próbnego ); dlaczego to nie liczy się jako czas wielomianowy?

Aby zrozumieć różnicę między czasem wielomianowym a czasem pseudo wielomianowym, musimy zacząć od sformalizowania, co oznacza „czas wielomianowy”.

Powszechną intuicją dotyczącą czasu wielomianowego jest „czas O (n ^k ) dla jakiegoś k”. Na przykład sortowanie przez wybór przebiega w czasie O (n ² ), który jest czasem wielomianowym, podczas gdy rozwiązanie TSP przy użyciu brutalnej siły wymaga czasu O (n · n!), Który nie jest czasem wielomianowym.

Wszystkie te środowiska wykonawcze odwołują się do zmiennej n, która śledzi rozmiar danych wejściowych. Na przykład w sortowaniu przez wybór n oznacza liczbę elementów w tablicy, podczas gdy w TSP n oznacza liczbę węzłów na grafie. W celu ujednolicenia definicji tego, co faktycznie oznacza „n” w tym kontekście, formalna definicja złożoności czasowej definiuje „rozmiar” problemu w następujący sposób:

Rozmiar wejścia do problemu to liczba bitów wymaganych do zapisania tego wejścia.

Na przykład, jeśli dane wejściowe do algorytmu sortowania są tablicą 32-bitowych liczb całkowitych, wówczas rozmiar danych wejściowych będzie wynosił 32n, gdzie n to liczba wpisów w tablicy. Na grafie z n węzłami i m krawędziami dane wejściowe mogą być określone jako lista wszystkich węzłów, po której następuje lista wszystkich krawędzi, co wymagałoby Ω (n + m) bitów.

Biorąc pod uwagę tę definicję, formalna definicja czasu wielomianowego jest następująca:

Algorytm działa w czasie wielomianowym, jeśli jego czas wykonania wynosi O (x ^k ) dla pewnej stałej k, gdzie x oznacza liczbę bitów danych wejściowych przekazanych do algorytmu.

Podczas pracy z algorytmami przetwarzającymi wykresy, listy, drzewa itp. Ta definicja jest mniej więcej zgodna z konwencjonalną definicją. Na przykład załóżmy, że masz algorytm sortowania, który sortuje tablice 32-bitowych liczb całkowitych. Jeśli użyjesz czegoś takiego jak sortowanie przez wybór, środowisko wykonawcze, jako funkcja liczby elementów wejściowych w tablicy, będzie wynosić O (n ² ). Ale jak n, liczba elementów w tablicy wejściowej, odpowiada liczbie bitów danych wejściowych? Jak wspomniano wcześniej, liczba bitów danych wejściowych będzie wynosić x = 32n. Dlatego, jeśli wyrazimy czas wykonania algorytmu w postaci x zamiast n, otrzymamy, że czas wykonania wynosi O (x ² ), a więc algorytm działa w czasie wielomianowym.

Podobnie, przypuśćmy, że na wykresie wykonujesz przeszukiwanie najpierw w głąb , co zajmuje czas O (m + n), gdzie m to liczba krawędzi na grafie, a n to liczba węzłów. Jak to się ma do liczby podanych bitów danych wejściowych? Cóż, jeśli założymy, że wejście jest określone jako lista przylegania (lista wszystkich węzłów i krawędzi), to jak wspomniano wcześniej, liczba bitów wejściowych będzie wynosić x = Ω (m + n). Dlatego środowisko wykonawcze będzie równe O (x), więc algorytm działa w czasie wielomianowym.

Sytuacja się jednak psuje, gdy zaczynamy mówić o algorytmach operujących na liczbach. Rozważmy problem sprawdzenia, czy liczba jest liczbą pierwszą, czy nie. Biorąc pod uwagę liczbę n, możesz sprawdzić, czy n jest liczbą pierwszą, używając następującego algorytmu:

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

Jaka jest więc złożoność czasowa tego kodu? Cóż, ta wewnętrzna pętla działa O (n) razy i za każdym razem wykonuje pewną ilość pracy, aby obliczyć n mod i (jako naprawdę konserwatywna górna granica, z pewnością można to zrobić w czasie O (n ³ )). Dlatego ten ogólny algorytm działa w czasie O (n ⁴ ) i prawdopodobnie znacznie szybciej.

W 2004 roku trzech informatyków opublikowało artykuł zatytułowany PRIMES jest w P, podając algorytm czasu wielomianowego do sprawdzania, czy liczba jest liczbą pierwszą. Uznano to za przełomowy wynik. Więc o co chodzi? Czy nie mamy już do tego algorytmu czasu wielomianowego, mianowicie powyższego?

Niestety nie. Pamiętaj, formalna definicja złożoności czasowej mówi o złożoności algorytmu jako funkcji liczby bitów danych wejściowych. Nasz algorytm działa w czasie O (n ⁴ ), ale co to jest w funkcji liczby bitów wejściowych? Cóż, wypisanie liczby n wymaga O (log n) bitów. Dlatego jeśli przyjmiemy, że x będzie liczbą bitów wymaganych do wypisania wejścia n, czas działania tego algorytmu wynosi w rzeczywistości O (2 ^4x ), co nie jest wielomianem w x.

To jest sedno rozróżnienia między czasem wielomianowym a czasem pseudo-wielomianowym. Z jednej strony naszym algorytmem jest O (n ⁴ ), które wygląda jak wielomian, ale z drugiej strony, zgodnie z formalną definicją czasu wielomianu, nie jest to czas wielomianowy.

Aby zorientować się, dlaczego algorytm nie jest algorytmem wielomianowym, pomyśl o następujących kwestiach. Załóżmy, że chcę, aby algorytm musiał wykonać dużo pracy. Jeśli napiszę takie dane wejściowe:

10001010101011

to zajmie trochę czasu, powiedzmy T, w najgorszym przypadku . Jeśli teraz dodam jeden bit na końcu numeru, w ten sposób:

100010101010111

Czas działania będzie teraz (w najgorszym przypadku) wynosić 2T. Mogę podwoić ilość pracy wykonywanej przez algorytm, dodając jeszcze jeden bit!

Algorytm działa w czasie pseudo wielomianu, jeśli czas wykonania jest jakimś wielomianem w wartości liczbowej wejścia , a nie w liczbie bitów wymaganych do jego przedstawienia. Nasz główny algorytm testujący jest algorytmem pseudopolimianu czasu, ponieważ działa w czasie O (n ⁴ ), ale nie jest algorytmem wielomianu, ponieważ w zależności od liczby bitów x wymaganych do wypisania danych wejściowych, czas wykonania wynosi O (2 ^4x ). Powodem, dla którego artykuł „PRIMES is in P” był tak znaczący, było to, że jego czas działania wynosił (w przybliżeniu) O (log ¹² n), co w funkcji liczby bitów wynosi O (x ¹² ).

Więc dlaczego to ma znaczenie? Cóż, mamy wiele algorytmów czasu pseudopolynomianu do faktoryzacji liczb całkowitych. Jednak te algorytmy są, mówiąc technicznie, algorytmami czasu wykładniczego. Jest to bardzo przydatne w kryptografii: jeśli chcesz używać szyfrowania RSA, musisz mieć zaufanie, że nie możemy łatwo uwzględniać liczb. Zwiększając liczbę bitów w liczbach do ogromnej wartości (powiedzmy 1024 bity), można sprawić, że ilość czasu, jaką musi zająć algorytm faktorowania pseudopolimianu, stanie się tak duża, że ​​byłoby całkowicie i całkowicie niewykonalne uwzględnienie liczby. Jeśli, z drugiej strony, możemy znaleźć algorytm faktoryzacji wielomianu w czasie , niekoniecznie tak jest. Dodanie większej liczby bitów może spowodować znaczny wzrost pracy, ale wzrost będzie tylko wzrostem wielomianowym, a nie wykładniczym.

To powiedziawszy, w wielu przypadkach algorytmy czasu pseudo wielomianowego są całkowicie dobre, ponieważ rozmiar liczb nie będzie zbyt duży. Na przykład sortowanie zliczające ma czas wykonania O (n + U), gdzie U jest największą liczbą w tablicy. Jest to czas pseudowielomianu (ponieważ wartość liczbowa U wymaga O (log U) bitów do wypisania, więc czas wykonywania jest wykładniczy pod względem wielkości wejściowej). Jeśli sztucznie ograniczymy U, aby U nie było zbyt duże (powiedzmy, jeśli pozwolimy U wynosić 2), to czas wykonania wynosi O (n), co w rzeczywistości jest czasem wielomianowym. Oto, jak działa sortowanie radix : przetwarzając liczby po jednym bicie, czas wykonania każdej rundy wynosi O (n), więc całkowity czas wykonania wynosi O (n log U). To faktycznie jest czas wielomianowy, ponieważ wypisanie n liczb do sortowania wykorzystuje Ω (n) bitów, a wartość log U jest wprost proporcjonalna do liczby bitów wymaganych do wypisania maksymalnej wartości w tablicy.

Mam nadzieję że to pomoże!

Pseudo-wielomianowa złożoność czasowa oznacza wielomian wartości / wielkości danych wejściowych, ale wykładniczy pod względem wielkości danych wejściowych.

Przez rozmiar rozumiemy liczbę bitów wymaganych do zapisania danych wejściowych.

Z pseudo-kodu plecaka możemy znaleźć złożoność czasową O (nW).

// Input:
// Values (stored in array v) 
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W) 
for w from 0 to W 
    do   m[0, w] := 0 
end for  
for i from 1 to n do  
        for j from 0 to W do
               if j >= w[i] then 
                      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 
              else 
                      m[i, j] := m[i-1, j]
              end if
       end for 
end for

Tutaj jednak W nie jest wielomianem długości wejścia, co czyni go pseudo-wielomianem.

Niech będzie liczbą bitów potrzebnych do reprezentacji W.

i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W  (because  2^(log(x)) = x)

Teraz running time of knapsack= O (nW) = O (n * 2 ^ s), co nie jest wielomianem.