Изысканность (теория сложности) - Sophistication (complexity theory)

В алгоритмическая теория информации, изысканность мера сложности, связанная с алгоритмическая энтропия.

Когда K является Колмогоровская сложность и c константа, изощренность Икс можно определить как^[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} _ {+} }.}$

Постоянная c называется значение. В S переменная пробегает конечные множества.

Интуитивно сложность измеряет сложность набора, «общим» членом которого является объект.

Смотрите также

• Логическая глубина

использованная литература

дальнейшее чтение

• Коппель, Моше (1995). Херкен, Рольф (ред.). "Структура". Универсальная машина Тьюринга (2-е изд.). Springer-Verlag New York, Inc .: 403–419. ISBN  3-211-82637-8.
• Антунес, Луис; Фортноу, Лэнс (30 августа 2007 г.). «Возвращение к изысканности» (PDF). Дои:10.1007 / s00224-007-9095-5. Цитировать журнал требует | журнал = (Помогите)
• Луис, Антунес; Баувенс, Бруно; Соуто, Андре; Тейшейра, Андрей (2013). «Изысканность vs логическая глубина». arXiv:1304.8046.

внешние ссылки

• Первый закон комплексодинамики

P ≟ NP

Эта теоретическая информатика –Связанная статья является заглушка. Вы можете помочь Википедии расширяя это.