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

Логическая глубина — это мера сложности отдельных строк, разработанная Чарльзом Х. Беннеттом на основе вычислительной сложности алгоритма, который может воссоздать заданный фрагмент информации. Он отличается от сложности по Колмогорову тем, что учитывает время вычисления алгоритма с почти минимальной длиной, а не длину минимального алгоритма.

Неформально, логическая глубина строки $x$ до уровня значимости $s$ это время, необходимое для вычисления $x$ по программе не более $s$ бит длиннее, чем самая короткая программа, вычисляющая $x$ . ^[1]

Формально пусть $p^{*}$ быть самой короткой программой, вычисляющей строку $x$ на каком-то универсальном компьютере $U$ . Тогда логическая глубина $x$ до уровня значимости $s$ дается ${\text{min}}\{T(p):(|p|-|p^{*}|<s)\wedge (U(p)=x)\},$ где $T(p)$ количество шагов вычислений, которые $p$ сделано на $U$ производить $x$ и остановиться.

См. также

Ссылки

^ Антунес, Луис; БААУЛЕНС, Бруно; СОУТО, Андре; ТЕЙШЕЙРА, Андрея (01 февраля 2017 г.). «Утонченность против логической глубины» . Теория вычислительных систем . 60 (2): 280–298. arXiv : 1304.8046 . дои : 10.1007/s00224-016-9672-6 . ISSN 1433-0490 . S2CID 253745548 .

Беннетт, Чарльз Х. (1988), «Логическая глубина и физическая сложность», Херкен, Рольф (редактор), Универсальная машина Тьюринга: обзор полувека , Oxford U. Press, стр. 227–257, CiteSeerX 10.1 .1.70.4331
Крейг, Эдвард (1998), «Вычислимость и информация, Раздел 6: Логическая глубина» , Философская энциклопедия Routledge, Vol. 10: Указатель , Тейлор и Фрэнсис, с. 481, ISBN 9780415073103

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .

[1] Антунес, Луис; БААУЛЕНС, Бруно; СОУТО, Андре; ТЕЙШЕЙРА, Андрея (01 февраля 2017 г.). «Утонченность против логической глубины» . Теория вычислительных систем . 60 (2): 280–298. arXiv : 1304.8046 . дои : 10.1007/s00224-016-9672-6 . ISSN 1433-0490 . S2CID 253745548 .

[1]