Sofistikovanost (teorie složitosti) - Sophistication (complexity theory)

v teorie algoritmických informací, sofistikovanost je míra složitosti související s algoritmická entropie.

Když K je Kolmogorovova složitost a C je konstanta, sofistikovanost X lze definovat jako^[1]

${ displaystyle operatorname {Soph} _ {c} (x): = inf { operatorname {K} (S): x in S land operatorname {K} (x mid S) geq přihlásit _ {2} (| S |) -c land | S | in mathbb {N} _ {+} }.}$

Konstanta C je nazýván význam. The S variabilní rozsahy přes konečné množiny.

Intuitivně sofistikovanost měří složitost sady, jejíž objekt je „obecným“ členem.

Viz také

• Logická hloubka

Reference

Další čtení

• Koppel, Moshe (1995). Herken, Rolf (ed.). "Struktura". Univerzální Turingův stroj (2. vydání). Springer-Verlag New York, Inc .: 403–419. ISBN  3-211-82637-8.
• Antunes, Luís; Fortnow, Lance (30. srpna 2007). „Sofistikovanost znovu navštívena“ (PDF). doi:10.1007 / s00224-007-9095-5. Citovat deník vyžaduje | deník = (Pomoc)
• Luís, Antunes; Bauwens, Bruno; Souto, André; Teixeira, Andreia (2013). "Sofistikovanost vs logická hloubka". arXiv:1304.8046.

externí odkazy

• První zákon komplexodynamiky