PolyL (Complexitat)

classe de complexitat

En teoria de la complexitat, la classe de complexitat PolyL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en un espai fitat per una funció polilogarítmica. Per tant es pot dir que PolyL = DSPACE ((log n)O(1)) on n és la mida de l'entrada i O(1) és una constant.[1]

Relació amb d'altres classes

modifica

Igual que LP, polyLQP.

Tot i això, l'única relació provada entre PolyL i P és que polyL ≠ P i es desconeix si polyL ⊊ P, si P ⊊ polyL o si una conté a l'altra.

Referències

modifica
  1. «Complexity Zoo:P - Complexity Zoo» (en anglès). Arxivat de l'original el 2018-01-19. [Consulta: 1r desembre 2018].