SL (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
[modifica]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:
Referències
[modifica]- ↑ 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, 1982-08, pàg. 161–187. DOI: 10.1016/0304-3975(82)90058-5. ISSN: 0304-3975.
- ↑ George, Michael Goderbauer, Stefan. «ECCC - TR04-094» (en anglès). [Consulta: 1r desembre 2018].
- ↑ Nisan, N.; Szemeredi, E.; Wigderson, A. «Undirected connectivity in O(log/sup 1.5/n) space» (en anglès). SFCS '92 Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. IEEE, 1992. DOI: 10.1109/sfcs.1992.267822.
- ↑ Nisan, Noam; Ta-Shma, Amnon «Symmetric logspace is closed under complement». STOC '95 Proceedings of the twenty-seventh annual ACM symposium on Theory of computing. ACM, 29-05-1995, pàg. 140–146. DOI: 10.1145/225058.225101.
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
