Nr 01 · Słownik · Teoria informatyki · Matematyka dyskretna i teoria obliczeń

Teoria zlozonosci klasy

20 pojęć w 9 podgrupach, z prostymi definicjami i źródłami.

Hierarchie · 2

  • 01hierarchia wielomianowaPH (polynomial hierarchy)Hierarchia klas złożoności uogólniających NP i coNP przez naprzemienne kwantyfikatory egzystencjalne i uniwersalne nad maszyną wyroczniową.
  • 02twierdzenie o hierarchii czasowejtime hierarchy theoremWynik mówiący, że przy większym ograniczeniu czasu maszyny rozstrzygają ściśle więcej problemów; gwarantuje istnienie problemów trudniejszych czasowo.

Klasy czasowe deterministyczne · 2

  • 01EXPTIMEKlasa problemów rozstrzygalnych przez deterministyczną maszynę Turinga w czasie wykładniczym, ograniczonym przez 2 do potęgi wielomianu od rozmiaru wejścia.
  • 02PP (PTIME)Klasa problemów decyzyjnych rozstrzygalnych przez deterministyczną maszynę Turinga w czasie wielomianowym względem rozmiaru wejścia.

Klasy czasowe niedeterministyczne · 2

  • 01coNPKlasa problemów, których dopełnienia należą do NP; obejmuje problemy z wielomianowo weryfikowalnym świadectwem odpowiedzi negatywnej.
  • 02NPNP (nondeterministic polynomial)Klasa problemów decyzyjnych weryfikowalnych w czasie wielomianowym, równoważnie rozstrzygalnych przez niedeterministyczną maszynę Turinga w czasie wielomianowym.

Klasy pamieciowe · 3

  • 01LOGSPACEL (LOGSPACE)Klasa problemów rozstrzygalnych przez deterministyczną maszynę Turinga używającą logarytmicznej pamięci roboczej względem rozmiaru wejścia.
  • 02NLNL (nondeterministic logspace)Klasa problemów rozstrzygalnych przez niedeterministyczną maszynę Turinga z logarytmiczną pamięcią roboczą; kluczowa dla problemu osiągalności w grafie.
  • 03PSPACEKlasa problemów decyzyjnych rozstrzygalnych przez deterministyczną maszynę Turinga z użyciem pamięci wielomianowej względem rozmiaru wejścia.

Klasy probabilistyczne · 2

  • 01BPPbounded-error probabilistic polynomialKlasa problemów rozstrzygalnych przez probabilistyczną maszynę Turinga w czasie wielomianowym z dwustronnym błędem ograniczonym poniżej 1/3.
  • 02RPrandomized polynomialKlasa problemów rozstrzygalnych w wielomianowym czasie przez maszynę probabilistyczną z jednostronnym błędem: nigdy nie myli się dla instancji negatywnych.

Miary zlozonosci · 2

  • 01złożoność czasowaMiara zasobu obliczeniowego określająca liczbę kroków elementarnych wykonywanych przez maszynę dla danych wejściowych, wyrażana jako funkcja rozmiaru wejścia.
  • 02złożoność pamięciowaMiara zasobu określająca maksymalną liczbę komórek pamięci roboczej używanych przez maszynę dla danych wejściowych, jako funkcja rozmiaru wejścia.

Notacja asymptotyczna · 1

  • 01notacja dużego OO(n) — Big-OAsymptotyczny zapis ograniczający tempo wzrostu funkcji od góry z dokładnością do stałej, używany do opisu skalowania zasobów algorytmu.

Redukcje · 2

  • 01redukcja Turingaredukcja CookaSprowadzenie jednego problemu do drugiego z wykorzystaniem wyroczni rozwiązującej problem docelowy wielokrotnie, mierzące względną trudność obliczeniową.
  • 02redukcja wielomianowaredukcja KarpaPrzekształcenie instancji jednego problemu w instancję drugiego, obliczalne w czasie wielomianowym i zachowujące odpowiedź, służące porównaniu trudności problemów.

Twardosc zupelnosc · 4

  • 01NP-trudnośćNP-hardWłasność problemu, do którego każdy problem z klasy NP daje się zredukować wielomianowo; problem co najmniej tak trudny jak wszystkie w NP.
  • 02NP-zupełnośćNP-completeWłasność problemu należącego do NP i jednocześnie NP-trudnego; reprezentuje najtrudniejsze problemy tej klasy.
  • 03PSPACE-zupełnośćPSPACE-completeWł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.
  • 04twierdzenie Cooka-LevinaWynik stwierdzający, że problem spełnialności formuł boolowskich (SAT) jest NP-zupełny, ustanawiający pierwszy problem NP-zupełny.

Pozostałe grupy — Matematyka dyskretna i teoria obliczeń

Grupa pojęć · Matematyka dyskretna i teoria obliczeń20 haseł