SL (Complexitat)
classe de complexitat
En teoria de la complexitat, la classe de complexitat SL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai log(n) tal que:[1][2]
- si la resposta és SI, existeix algun camí de còmput que accepta l'entrada
- si la resposta és NO, tots els canins han rebutjat l'entrada
- si la màquina pot fer una transició no determinista entre una configuració A i una configuració B, també pot fer la transició simètrica (fer una transició entre la configuració B a la configuració A).
Aquesta màquina es coneix com a màquina de Turing simètrica.[3]
Relació amb d'altres classes
El 2004 Omer Reingold va demostrar que la classe SL = L. Això ve a dir que la condició de simetria de la màquina de Turing no determinista la converteix en una màquina de Turing determinista.[4]
SL és dins de DSPACE (log3/2n).[5]
També se sap que SL és co-SL i per tant que SLSL = SL.[6]
Per tant es te que:
