Pamięć może być ważniejszą granicą niż czas
Teoria złożoności nie mierzy wyłącznie czasu. Klasa PSPACE obejmuje problemy rozstrzygalne przy użyciu pamięci ograniczonej wielomianem długości wejścia, nawet jeśli obliczenie może trwać bardzo długo. Klasycznym problemem PSPACE-zupełnym jest TQBF — sprawdzanie prawdziwości w pełni skwantyfikowanych formuł boolowskich. Prosty algorytm rekurencyjny może rozgałęziać się na wiele przypisań, ale nie musi przechowywać całego drzewa naraz: eksploruje gałęzie po kolei i ponownie wykorzystuje pamięć. To pokazuje, że czas i pamięć są różnymi zasobami. Program może wykonywać olbrzymią liczbę kroków, a mimo to utrzymywać stosunkowo niewielki stan roboczy.
Dwa różne budżety
Komputer zużywa co najmniej dwa podstawowe zasoby: czas i pamięć. Algorytm może być szybki, ale pamięciożerny, albo powolny, lecz używać mało pamięci. Klasy złożoności przestrzennej formalizują drugi wymiar. PSPACE to unia problemów rozwiązywalnych przez deterministyczną maszynę przy użyciu O(n^c) komórek pamięci roboczej dla pewnej stałej c.
TQBF jako modelowy problem
TQBF pyta, czy formuła boolowska poprzedzona naprzemiennymi kwantyfikatorami ∃ i ∀ jest prawdziwa. Na przykład wybór wartości dla zmiennej egzystencjalnej może zależeć od wcześniejszych zmiennych uniwersalnych. Problem jest PSPACE-zupełny: należy do PSPACE i każdy problem z PSPACE można do niego wielomianowo zredukować.
Jak oszczędza się pamięć
Najprostsza ewaluacja może rekurencyjnie ustawiać pierwszą zmienną na 0, obliczać wynik, następnie na 1 i obliczać drugi wynik, po czym łączyć rezultaty zależnie od kwantyfikatora. Liczba gałęzi może być wykładnicza, ale po zakończeniu jednej gałęzi jej szczegółowa historia nie musi pozostawać w pamięci. Princeton opisuje implementację TQBF zużywającą przestrzeń liniową w rozmiarze formuły przez ponowne używanie tablicy częściowego przypisania.
Mało pamięci nie oznacza mało pracy
Jeżeli algorytm wielokrotnie wraca do podobnych stanów albo przechodzi przez ogromne drzewo decyzji sekwencyjnie, czas może być wielki mimo niewielkiej pamięci. To analogia do człowieka rozwiązującego labirynt z kartką: można mieć mało miejsca na notatki i chodzić bardzo długo. Złożoność przestrzenna pozwala badać sytuacje, w których ograniczeniem fizycznym jest pojemność pamięci, a nie tylko liczba operacji.
Dlaczego osobna analiza ma sens
Urządzenia wbudowane, systemy strumieniowe i obliczenia na ogromnych zbiorach danych często mają restrykcyjny budżet pamięci. Z drugiej strony nawet w teorii relacje między klasami czasu i przestrzeni ujawniają subtelną strukturę obliczeń. „Czy problem jest trudny?” jest więc pytaniem niepełnym bez dopowiedzenia: trudny pod względem jakiego zasobu?
Gdzie PSPACE leży na mapie klas
Każde obliczenie wielomianowego czasu może wykorzystać co najwyżej wielomianową liczbę odwiedzonych komórek pamięci, dlatego problemy z P mieszczą się w PSPACE; również NP zawiera się w PSPACE. Nie znamy jednak dowodu, że NP i PSPACE są różne. PSPACE-zupełność TQBF oznacza coś analogicznego do NP-zupełności SAT, lecz dla całej klasy problemów wielomianowej przestrzeni: wielomianowy algorytm przestrzenny już istnieje, a kompletność opisuje jego centralną rolę w tej klasie. To przypomina, że mapa złożoności nie jest jedną linią od „łatwych” do „trudnych” — różne ograniczenia zasobów tworzą nakładające się klasy i wiele nierozstrzygniętych relacji.
Mała przestrzeń ogranicza również liczbę odróżnialnych stanów
Jeżeli maszyna używa tylko wielomianowej pamięci, liczba możliwych konfiguracji jest skończona i co najwyżej wykładnicza w rozmiarze wejścia. To pomaga zrozumieć, dlaczego obliczenie przestrzenne może trwać bardzo długo, ale nadal podlega silnym ograniczeniom strukturalnym. Algorytm może wielokrotnie odwiedzać różne konfiguracje, przechowywać tylko bieżącą gałąź i odzyskiwać pamięć po powrocie. Przestrzeń opisuje więc liczbę informacji utrzymywanych jednocześnie, a nie całkowitą liczbę wykonanych kroków.