Сжатие энтропии
В математике и теоретической информатике сжатие энтропии — это теоретико-информационный метод доказательства завершения случайного процесса , первоначально использованный Робином Мозером для доказательства алгоритмической версии локальной леммы Ловаса . [1] [2]
Описание
[ редактировать ]Чтобы использовать этот метод, доказывается, что история данного процесса может быть записана таким эффективным способом, что состояние процесса в любой прошлый момент может быть восстановлено из текущего состояния и этой записи, и что количество Дополнительная информация, записываемая на каждом этапе процесса, (в среднем) меньше количества новой информации, случайно генерируемой на каждом этапе. Возникающее в результате растущее несоответствие общего содержания информации никогда не может превысить фиксированный объем информации в текущем состоянии, из чего следует, что процесс в конечном итоге должен завершиться. Этот принцип можно формализовать и сделать строгим, используя сложность Колмогорова . [3]
Пример
[ редактировать ]Пример, приведенный обоими Fortnow [3] и Тао [4] касается проблемы булевой выполнимости для булевых формул в конъюнктивной нормальной форме с одинаковым размером предложений. Эти проблемы могут быть параметризованы двумя числами ( k , t ), где k — количество переменных в каждом предложении, а t — максимальное количество различных предложений, в которых может появиться любая переменная. Если переменным присваиваются значения true или false случайным образом, тогда событие невыполнения условия происходит с вероятностью 2 - к и каждое событие независимо от всех других событий, кроме r = k ( t − 1). следует Из локальной леммы Ловаса , что если t достаточно мало, чтобы r < 2 к / e (где e — основание натурального логарифма ), то решение всегда существует. Следующий алгоритм можно продемонстрировать с использованием энтропийного сжатия для поиска такого решения, когда r меньше этой границы в постоянный коэффициент:
- Выберите случайное задание истины
- Пока существует невыполненное условие C , вызовите рекурсивное исправление подпрограммы с C в качестве аргумента. Эта подпрограмма выбирает новое случайное присвоение истинности переменным в C , а затем рекурсивно вызывает ту же самую подпрограмму для всех невыполненных предложений (возможно, включая C ), которые используют одну и ту же переменную с C. сам
Этот алгоритм не может завершиться, если входная формула не является выполнимой, поэтому доказательство того, что он завершается, также является доказательством существования решения. Каждая итерация внешнего цикла уменьшает количество невыполненных предложений (это приводит к тому, что C становится удовлетворенным, не делая при этом какое-либо другое предложение невыполненным), поэтому ключевой вопрос заключается в том, завершается ли подпрограмма исправления или она может перейти в бесконечную рекурсию . [3]
Чтобы ответить на этот вопрос, рассмотрим, с одной стороны, количество случайных битов, генерируемых на каждой итерации подпрограммы исправления ( k бит на предложение), а с другой стороны, количество битов, необходимых для записи истории этого алгоритма таким образом. что любое прошлое состояние может быть сгенерировано. Чтобы записать эту историю, мы можем сохранить текущее присвоение истинности ( n бит), последовательность начальных аргументов функции исправления ( m log m бит, где m — количество предложений во входных данных), а затем последовательность записей. это либо указывает на то, что рекурсивный вызов fix вернулся, либо что он, в свою очередь, выполнил еще один вызов одного из предложений r + 1 (включая сам C ), которые используют общую переменную с C . Для каждой записи существует r + 2 возможных результата, поэтому количество битов, необходимых для хранения записи, равно log r + O (1). [3]
Эту информацию можно использовать для восстановления последовательности предложений, заданных в качестве рекурсивных аргументов для fix . Истинные назначения на каждом этапе этого процесса затем могут быть восстановлены (без необходимости записи какой-либо дополнительной информации), продвигаясь назад по этой последовательности предложений, используя тот факт, что каждое предложение ранее было невыполнимо, чтобы вывести значения всех его переменных до этого. к каждому вызову исправления . Таким образом, после f вызовов fix алгоритм сгенерирует fk случайных битов, но вся его история (включая эти сгенерированные биты) может быть восстановлена из записи, которая использует только m log m + n + f log r + O ( f ) битов. . Отсюда следует, что когда r достаточно мало, чтобы сделать log r + O (1) < k , подпрограмма fix может выполнить только O ( m log m + n ) рекурсивных вызовов в течение всего алгоритма. [3]
История
[ редактировать ]Название «энтропийное сжатие» было дано этому методу в блоге Теренса Тао. [4] и с тех пор использовался для этого другими исследователями. [5] [6] [7]
Мозера Исходная версия алгоритмической локальной леммы Ловаса , использующая этот метод, достигла более слабых границ, чем исходная локальная лемма Ловаса , которая изначально была сформулирована как теорема существования без конструктивного метода поиска объекта, существование которого она доказывает. Позже Мозер и Габор Тардос использовали тот же метод для доказательства версии алгоритмической локальной леммы Ловаса, которая соответствует границам исходной леммы. [8]
С момента открытия метода сжатия энтропии он также использовался для получения более сильных оценок для некоторых задач, чем те, которые дает локальная лемма Ловаса. Например, для задачи ациклической раскраски ребер графов с максимальной степенью Δ сначала с помощью локальной леммы было показано, что всегда существует раскраска с 64 Δ цветами, а позже с использованием более сильной версии локальной леммы это было улучшено до 9,62. Δ. Однако более прямой аргумент с использованием энтропийного сжатия показывает, что существует раскраска, использующая только 4 (Δ - 1) цвета, и, более того, эту раскраску можно найти за рандомизированное полиномиальное время. [6]
Ссылки
[ редактировать ]- ^ Мозер, Робин А. (2009), «Конструктивное доказательство локальной леммы Ловаса», STOC'09 — Труды Международного симпозиума ACM 2009 года по теории вычислений , Нью-Йорк: ACM, стр. 343–350, arXiv : 0810.4812 , doi : 10.1145/1536414.1536462 , ISBN 978-1-60558-506-2 , МР 2780080 .
- ^ Липтон, Р.Дж. (2 июня 2009 г.), «Метод Мозера для ограничения программного цикла» , «Потерянное письмо Гёделя» и P=NP .
- ^ Jump up to: Перейти обратно: а б с д и Фортнау, Лэнс (2 июня 2009 г.), «Колмогоровское доказательство локальной леммы Ловаса» , Вычислительная сложность .
- ^ Jump up to: Перейти обратно: а б Тао, Теренс (5 августа 2009 г.), «Аргумент сжатия энтропии Мозера» , Что нового .
- ^ Дуймович, Вида ; Жоре, Гвенаэль; Козик, Якуб; Вуд, Дэвид Р. (2016), «Неповторяющаяся раскраска посредством энтропийного сжатия», Combinatorica , 36 (6): 661–686, arXiv : 1112.5524 , Bibcode : 2011arXiv1112.5524D , doi : 10.1007/s00493-015-3070-6 .
- ^ Jump up to: Перейти обратно: а б Эспере, Луи; Парро, Алин (2013), «Ациклическая раскраска ребер с использованием энтропийного сжатия», Европейский журнал комбинаторики , 34 (6): 1019–1027, arXiv : 1206.1535 , doi : 10.1016/j.ejc.2013.02.007 , MR 3037985 .
- ^ Охем, Паскаль; Pinlou, Alexandre (2014), «Применение сжатия энтропии в предотвращении узора» , Electronic Journal of Combinatorics , 21 (2), статья 2.7, Arxiv : 1301.1873 , Bibcode : 2013Arxiv1301.1873o , doi : 10.37236/3038 , Mr 3210641 .
- ^ Мозер, Робин А.; Тардос, Габор (2010), «Конструктивное доказательство общей локальной леммы Ловаса», Журнал ACM , 57 (2), ст. 11, arXiv : 0903.0544 , doi : 10.1145/1667053.1667060 , MR 2606086 .