Прошу прощения, это немного "мягкий" вопрос.
Теория информации не имеет понятия вычислительной сложности. Например, экземпляр SAT или экземпляр SAT плюс бит, указывающий на выполнимость, несут одинаковое количество информации.
Есть ли способ формализовать понятие «полиномиально узнаваемый»?
Такая структура могла бы определить, например, понятие расхождения полиномиального KL между случайной величиной X относительно Y как число битов, необходимых для вычисления X за полиномиальное время, заданное Y.
Аналогично, энтропия случайной величины X может быть определена как количество битов, необходимых для кодирования X таким образом, который может быть декодирован за полиномиальное время.
Было ли изучено такое обобщение? Можно ли сделать это последовательным?
Ответы:
Да. Ограниченная во времени колмогоровская сложность является как минимум одним из таких «обобщений» (хотя, строго говоря, это не обобщение, а родственное понятие). Исправить универсальный станок ТьюрингаU , т ( н ) временная колмогоровская сложность струны Икс заданная строка Y (относительно U ), обозначается КTU( х | у) (индекс U часто подавляется) определяется как самая короткая строка п («программа» для U ) такой что U( р , у) = х и такой, что вычисление U( р , у) занимает максимум т ( | х | ) время. Если вы примете это как определение «условной информации», то вы также можете определить все обычные понятия из теории информации.
Однако в этой ограниченной во времени установке известно, что не все обычные теоремы теории информации известны. Например, известно, что симметрия информации имеет место для обычной колмогоровской сложности (без временной привязки), но не известна для ограниченной по времени. См., Например, главу 6 тезиса Троя Ли .
Если вы обеспокоены тем, что это относится к строкам, а не к распределениям, я предлагаю прочитать следующие статьи, в которых говорится, что на самом деле сложность струн Колмогорова и энтропия распределений Шеннона очень тесно связаны:
Грюнвальд и Витаньи. Информация Шеннона и колмогоровская сложность
Молоток, Ромащенко, Шень, Верещагин. Неравенства для энтропии Шеннона и колмогоровской сложности .
(С другой стороны, есть некоторые свойства, которые, как известно, не разделяются между ними, см. Мучник и Верещагин, Энтропия Шеннона против Колмогорова .)
источник
Одна из проблем заключается в том, что многие из теорем, к которым мы привыкли в теории информации, не выполняются в вычислительном мире. Следовательно, даже если мы формализуем вычислительный аналог энтропии, полученная теория может больше не выглядеть как теория информации.
Например, еслие является детерминированной функцией, то ЧАС( ф( Х) ) ≤ H( Х) , Однако, для любого правдоподобного вычислительного понятия энтропии это больше не будет иметь место: например, подумайте о псевдослучайном генераторе, который растягивает короткое начальное число в длинный псевдослучайный вывод. Любым мыслимым определением вычислительной энтропии я могу себе представить, что длинный псевдослучайный выход будет иметь большую вычислительную энтропию (он вычислительно неотличим от равномерного распределения на этих длинных строках), нарушая тем самымЧАС( ф( Х) ) ≤ H( Х) ,
источник
Я не знаю об информационно-теоретической вычислительной модели, но есть очевидные применения теории информации к вычислительной сложности.
Например, классическийжурнал nN Нижняя граница сортировки на основе сравнения основана на теоретико-информационном аргументе о высоте дерева решений, необходимой для различения всех возможных порядков входных данных. Аналогичным образом можно сделать тривиальные теоретико-информационные оценки вычислительной сложности поиска, статистики заказов, среднего и т. Д.
Более типично, теоретико-информационные результаты могут служить нижней границей сложности вычислений. Например, «теоретико-информационный» результат Яо о сложности связи {1} подразумевает вычислительные нижние границы для определения, равны ли два набора. Более сложные приложения сложности связи обеспечивают пространственно-временные компромиссы для машин Тьюринга {2}.
{1} Яо, Эндрю Чи-Чи. «Некоторые вопросы сложности, связанные с распределенными вычислениями (предварительный отчет)». Материалы одиннадцатого ежегодного симпозиума ACM по теории вычислений. ACM, 1979.
{2} Эяль Кушилевиц: Коммуникационная сложность. Достижения в области компьютеров 44: 331-360 (1997).
источник