PolyL - PolyL

v teorie výpočetní složitosti, polyL je třída složitosti z rozhodovací problémy to lze vyřešit na a deterministický Turingův stroj algoritmem, jehož složitost prostoru je ohraničen a polylogaritmický funkce ve velikosti vstupu. Jinými slovy, polyL = DSPACE((logn)^{O (1)}), kde n označuje velikost vstupu a Ó (1) označuje konstantu.

Stejně jako L ⊆ P, polyL ⊆ QP. Jediný prokázaný vztah mezi polyL a P je to polyL ≠ P; není známo, zda polyL ⊊ P, pokud P ⊊ polyL, nebo pokud žádný z nich není obsažen v druhém. Jeden důkaz toho polyL ≠ P je to P má úplný problém pod logaritmický prostor mnoho-jedna redukce ale polyL není kvůli věta o hierarchii prostoru Věta o vesmírné hierarchii to zaručuje DSPACE(log^d n) ⊊ DSPACE(log^{d + 1} n) pro všechna celá čísla d> 0. Pokud polyL měl úplný problém, nazvěte to A, to by byl prvek DSPACE(log^k n) pro celé číslo k> 0. Předpokládejme problém B je prvek DSPACE(log^{k + 1} n) \ DSPACE(log^k n). Předpoklad, že A je kompletní znamená následující O (log^k n) vesmírný algoritmus pro B: snížit B na A v logaritmickém prostoru, pak se rozhodněte A v O (log^k n) prostor. To z toho vyplývá B je prvek DSPACE(log^k n) a proto porušuje teorém o hierarchii prostoru.

externí odkazy

• Složitost Zoo: polyL