Back إس إل (تعقيد حسابي) Arabic SL (complexity) English SL (clase de complejidad) Spanish SL (計算複雑性理論) Japanese Complexidade SL Portuguese
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]
- ↑ H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821.
- ↑ «Complexity Zoo:S - Complexity Zoo» (en anglès). Arxivat de l'original el 2016-08-27. [Consulta: 1r desembre 2018].
- ↑ Lewis, Harry R.; Papadimitriou, Christos H. «Symmetric space-bounded computation». Theoretical Computer Science, 19, 2, 8-1982, pàg. 161–187. DOI: 10.1016/0304-3975(82)90058-5. ISSN: 0304-3975.