Vés al contingut

PolyL (Complexitat)

De la Viquipèdia, l'enciclopèdia lliure

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].