Sofisticação (teoria da complexidade)

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

$\operatorname {Soph} _{c}(x):=\inf\{\operatorname {K} (S):x\in S\land \operatorname {K} (x\mid S)\geq \log _{2}(|S|)-c\land |S|\in \mathbb {N} _{+}\}.$

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

• Profundidade lógica

Referências

Bibliografia

• 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

• «A Primeira Lei da Complexodinâmica» (em inglês)