DAA - Złożoność kosmiczna

W tym rozdziale omówimy złożoność problemów obliczeniowych w odniesieniu do ilości miejsca wymaganego przez algorytm.

Złożoność przestrzeni ma wiele wspólnych cech ze złożonością czasową i służy jako dalszy sposób klasyfikowania problemów według ich trudności obliczeniowych.

Co to jest złożoność przestrzeni?

Złożoność przestrzeni to funkcja opisująca ilość pamięci (przestrzeni), jaką zajmuje algorytm, w kategoriach ilości danych wejściowych do algorytmu.

Często o tym mówimy extra memorypotrzebne, nie licząc pamięci potrzebnej do przechowywania samego wejścia. Ponownie, do pomiaru tego używamy jednostek naturalnych (ale o stałej długości).

Możemy używać bajtów, ale łatwiej jest użyć, powiedzmy, liczby użytych liczb całkowitych, liczby struktur o stałej wielkości itp.

Ostatecznie funkcja, którą wymyślimy, będzie niezależna od rzeczywistej liczby bajtów potrzebnych do reprezentacji jednostki.

Złożoność przestrzeni jest czasami pomijana, ponieważ wykorzystywana przestrzeń jest minimalna i / lub oczywista, jednak czasami staje się tak ważna, jak złożoność czasowa

Definicja

Pozwolić M być deterministą Turing machine (TM)który zatrzymuje się na wszystkich wejściach. Złożoność przestrzeniM jest funkcją $ f \ colon N \ rightarrow N $, gdzie f(n) to maksymalna liczba komórek taśmy i M skanuje dowolne dane wejściowe o długości M. Jeśli złożoność przestrzeniM jest f(n), możemy to powiedzieć M działa w kosmosie f(n).

Szacujemy złożoność przestrzenną maszyny Turinga za pomocą notacji asymptotycznej.

Niech $ f \ colon N \ rightarrow R ^ + $ będzie funkcją. Klasy złożoności przestrzeni można zdefiniować w następujący sposób -

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE jest klasą języków, które są rozstrzygalne w przestrzeni wielomianowej na deterministycznej maszynie Turinga.

Innymi słowy, PSPACE = U_k SPACE (n^k)

Twierdzenie Savitcha

Jednym z najwcześniejszych twierdzeń związanych ze złożonością przestrzeni jest twierdzenie Savitcha. Zgodnie z tym twierdzeniem maszyna deterministyczna może symulować maszyny niedeterministyczne, wykorzystując niewielką ilość miejsca.

Wydaje się, że w przypadku złożoności czasowej taka symulacja wymaga wykładniczego wydłużenia czasu. W przypadku złożoności przestrzeni to twierdzenie pokazuje, że każda niedeterministyczna maszyna Turinga, która używaf(n) przestrzeń można przekształcić w deterministyczną pamięć TM, która używa f²(n) przestrzeń.

Stąd twierdzenie Savitcha stwierdza, że dla dowolnej funkcji $ f \ colon N \ rightarrow R ^ + $, gdzie $ f (n) \ geqslant n $

NSPACE(f(n)) ⊆ SPACE(f(n))