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

${\mathrm{Soph}}_c(x):=\inf \{\mathrm{K}(S):x\in S\wedge \mathrm{K}(x\mid S)\ge {\log }_2(|S|)-c\wedge |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

Bibliografia

• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar arXiv

Ligações externas

• Predefinição:Link