Sofisticação (teoria da complexidade)

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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

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

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre ciência da computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.