Mostrar código-fonte de 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<ref>{{citar periódico|título= Sophistication as Randomness Deficiency |último1 = Mota |primeiro1 = Francisco |último2 = Aaronson |primeiro2 = Scott |último3 = Antunes |primeiro3 = Luís |último4 = Souto |primeiro4 = André |url = http://www.scottaaronson.com/papers/DCFS-Final.pdf |doi = 10.1007/978-3-642-39310-5_17 }}</ref>

: <math>\operatorname{Soph}_c(x) := \inf \{ \operatorname{K}(S) : x \in S \land \operatorname{K}(x\mid S) \ge \log_2(|S|) - c \land |S| \in \mathbb{N}_+ \}.</math>

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 ===
* {{citar periódico|último1 = Koppel |primeiro1 = Moshe |título= Structure |obra= The Universal Turing Machine (2Nd Ed.) |editor = Herken, Rolf |ano= 1995 |isbn = 3-211-82637-8 |páginas= 403–419 |publicado= Springer-Verlag New York, Inc. }}
* {{citar periódico|último1 = Antunes |primeiro1 = Luís |último2 = Fortnow |primeiro2 = Lance |título= Sophistication Revisited |data=30 de agosto de 2007 |url = http://people.cs.uchicago.edu/~fortnow/papers/soph.pdf |doi = 10.1007/s00224-007-9095-5 }}
* {{citar arXiv|último1 =Luís |primeiro1 =Antunes |primeiro2 =Bruno |último2 =Bauwens |primeiro3 =André |último3 =Souto |primeiro4 =Andreia |último4 =Teixeira |eprint=1304.8046 |título=Sophistication vs Logical Depth |class= |ano=2013}}

== Ligações externas ==
* {{Link|idioma=en|http://www.scottaaronson.com/blog/?p=762|título=A Primeira Lei da Complexodinâmica}}

{{Portal3|Tecnologias de informação}}
{{Esboço-ciência-da-computação}}

[[Categoria:Teoria da informação]]