Teoria zlozonosci klasy

Hierarchia klas złożoności uogólniających NP i coNP przez naprzemienne kwantyfikatory egzystencjalne i uniwersalne nad maszyną wyroczniową.

Wynik mówiący, że przy większym ograniczeniu czasu maszyny rozstrzygają ściśle więcej problemów; gwarantuje istnienie problemów trudniejszych czasowo.

Klasa problemów rozstrzygalnych przez deterministyczną maszynę Turinga w czasie wykładniczym, ograniczonym przez 2 do potęgi wielomianu od rozmiaru wejścia.

Klasa problemów decyzyjnych rozstrzygalnych przez deterministyczną maszynę Turinga w czasie wielomianowym względem rozmiaru wejścia.

Klasa problemów, których dopełnienia należą do NP; obejmuje problemy z wielomianowo weryfikowalnym świadectwem odpowiedzi negatywnej.

Klasa problemów decyzyjnych weryfikowalnych w czasie wielomianowym, równoważnie rozstrzygalnych przez niedeterministyczną maszynę Turinga w czasie wielomianowym.

Klasa problemów rozstrzygalnych przez deterministyczną maszynę Turinga używającą logarytmicznej pamięci roboczej względem rozmiaru wejścia.

Klasa problemów rozstrzygalnych przez niedeterministyczną maszynę Turinga z logarytmiczną pamięcią roboczą; kluczowa dla problemu osiągalności w grafie.

Klasa problemów decyzyjnych rozstrzygalnych przez deterministyczną maszynę Turinga z użyciem pamięci wielomianowej względem rozmiaru wejścia.

Klasa problemów rozstrzygalnych przez probabilistyczną maszynę Turinga w czasie wielomianowym z dwustronnym błędem ograniczonym poniżej 1/3.

Klasa problemów rozstrzygalnych w wielomianowym czasie przez maszynę probabilistyczną z jednostronnym błędem: nigdy nie myli się dla instancji negatywnych.

Miara zasobu obliczeniowego określająca liczbę kroków elementarnych wykonywanych przez maszynę dla danych wejściowych, wyrażana jako funkcja rozmiaru wejścia.

Miara zasobu określająca maksymalną liczbę komórek pamięci roboczej używanych przez maszynę dla danych wejściowych, jako funkcja rozmiaru wejścia.

Asymptotyczny zapis ograniczający tempo wzrostu funkcji od góry z dokładnością do stałej, używany do opisu skalowania zasobów algorytmu.

Sprowadzenie jednego problemu do drugiego z wykorzystaniem wyroczni rozwiązującej problem docelowy wielokrotnie, mierzące względną trudność obliczeniową.

Przekształcenie instancji jednego problemu w instancję drugiego, obliczalne w czasie wielomianowym i zachowujące odpowiedź, służące porównaniu trudności problemów.

Własność problemu, do którego każdy problem z klasy NP daje się zredukować wielomianowo; problem co najmniej tak trudny jak wszystkie w NP.

Własność problemu należącego do NP i jednocześnie NP-trudnego; reprezentuje najtrudniejsze problemy tej klasy.

Własność problemu należącego do PSPACE i będącego co najmniej tak trudnym jak każdy inny problem tej klasy względem redukcji wielomianowej.

Wynik stwierdzający, że problem spełnialności formuł boolowskich (SAT) jest NP-zupełny, ustanawiający pierwszy problem NP-zupełny.