Sofisticação (teoria da complexidade)
Aspeto
Na Teoria Algorítmica da Informação, sofisticação é uma medida de complexidade relacionada a Complexidade de Kolmogorov.
Quando K é a Complexidade de Kolmogorov e c é uma constante, o nível de sofisticação de x pode ser definida como[1]
Onde a constante c é chamada de significado e a variável S varia sobre conjuntos finitos.
Intuitivamente, sofisticação mede a complexidade de um conjunto do qual o objeto é um membro "genérico".
Ver também
[editar | editar código-fonte]Referências
- ↑ Mota, Francisco; Aaronson, Scott; Antunes, Luís; Souto, André. «Sophistication as Randomness Deficiency» (PDF). doi:10.1007/978-3-642-39310-5_17
Bibliografia
[editar | editar código-fonte]- Koppel, Moshe (1995). Herken, Rolf, ed. «Structure». Springer-Verlag New York, Inc. The Universal Turing Machine (2Nd Ed.): 403–419. ISBN 3-211-82637-8
- Antunes, Luís; Fortnow, Lance (30 de agosto de 2007). «Sophistication Revisited» (PDF). doi:10.1007/s00224-007-9095-5
- Luís, Antunes; Bauwens, Bruno; Souto, André; Teixeira, Andreia (2013). «Sophistication vs Logical Depth». arXiv:1304.8046
Ligações externas
[editar | editar código-fonte]- «A Primeira Lei da Complexodinâmica» (em inglês)