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[1]

${\displaystyle \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".