Метод несжимаемости - Incompressibility method

В математика, то метод несжимаемости это доказательство метод как вероятностный метод, метод подсчета или принцип голубятни. Чтобы доказать, что объект определенного класса (в среднем) удовлетворяет определенному свойству, выберите объект этого класса, который несжимаемый. Если он не удовлетворяет свойству, его можно сжать вычислимый кодирование. Поскольку в целом можно доказать, что почти все объекты в данном классе несжимаемы, аргумент демонстрирует, что почти все объекты в классе имеют соответствующее свойство (а не только среднее значение). Выбрать несжимаемый объект неэффективно и не может быть выполнено с помощью компьютерной программы. Однако простой аргумент подсчета обычно показывает, что почти все объекты данного класса могут быть сжаты только несколькими биты (несжимаемы).

История

Метод несжимаемости зависит от объективного, фиксированного представления о несжимаемости. Такое понятие было дано Колмогоровская сложность теория, названная в честь Андрей Колмогоров.^[1]

Одним из первых применений метода несжимаемости с колмогоровской сложностью в теории вычислений было доказательство того, что время работы однопленочной ленты Машина Тьюринга квадратичен для принятия палиндромного языка и алгоритмы сортировки требуется по крайней мере ${\displaystyle n\log n}$ время сортировать ${\displaystyle n}$ Предметы.^[2] Одна из первых влиятельных статей, использующих метод несжимаемости, была опубликована в 1980 году.^[3] Метод был применен к ряду полей, и его название было придумано в учебнике.^[4]

Приложения

Теория чисел

Согласно элегантный Евклидов доказательство, существует бесконечное количество простые числа. Бернхард Риманн продемонстрировал, что количество простых чисел меньше данного числа связано с нулями Дзета-функция Римана. Жак Адамар и Шарль Жан де ла Валле-Пуссен в 1896 году доказал, что это число простых чисел асимптотический к ${\displaystyle n/\ln n}$; видеть Теорема о простых числах (использовать ${\displaystyle \ln }$ для натурального логарифма ${\displaystyle \log }$ для двоичного логарифма). Используя метод несжимаемости, Г. Дж. Чайтин утверждал следующее: каждый ${\displaystyle n}$ можно описать простые множители ${\displaystyle n=p_{1}^{n_{1}}\cdots p_{k}^{n_{k}}}$ (что уникально), где ${\displaystyle p_{1},\ldots ,p_{k}}$ первые ${\displaystyle k}$ простые числа, которые (не более) ${\displaystyle n}$ и экспоненты (возможно) 0. Каждый показатель (не более) ${\displaystyle \log n}$, и может быть описан ${\displaystyle \log \log n}$ биты. Описание ${\displaystyle n}$ может быть дан в ${\displaystyle k\log \log n}$ бит, если мы знаем значение ${\displaystyle \log \log n}$ (что позволяет разбирать последовательные блоки показателей). Описать ${\displaystyle \log \log n}$ требуется только ${\displaystyle \log \log \log n}$ биты. Используя несжимаемость большинства положительных целых чисел, для каждого ${\displaystyle k>0}$ есть положительное целое число ${\displaystyle n}$ двоичной длины ${\displaystyle l\approx \log n}$ который нельзя описать менее чем ${\displaystyle l}$ биты. Это показывает, что количество простых чисел, ${\displaystyle \pi (n)}$ меньше, чем ${\displaystyle n}$, удовлетворяет

${\displaystyle \pi (n)\geq {\frac {\log n}{\log \log n}}-o(1).}$

Более изощренный подход, приписываемый Петру Берману (настоящее доказательство частично принадлежит Джону Тромпу), описывает каждую несжимаемую ${\displaystyle n}$ к ${\displaystyle k}$ и ${\displaystyle n/p_{k}}$, куда ${\displaystyle p_{k}}$ это наибольшее простое число, делящее ${\displaystyle n}$. С ${\displaystyle n}$ несжимаемый, длина этого описания должна превышать ${\displaystyle \log n}$. Чтобы разобрать первый блок описания ${\displaystyle k}$ должно быть указано в виде префикса ${\displaystyle P(k)=\log k+\log \log k+\log \varepsilon (k)}$, куда ${\displaystyle \varepsilon (k)}$ - произвольная малая положительная функция. Следовательно, ${\displaystyle \log p_{k}\leq P(k)}$. Следовательно, ${\displaystyle p_{k}\leq n_{k}}$ с ${\displaystyle n_{k}=\varepsilon (k)k\log k}$ для особой последовательности значений ${\displaystyle n_{1},n_{2},\ldots }$. Это показывает, что приведенное ниже выражение справедливо для этой специальной последовательности, а простое расширение показывает, что оно справедливо для каждой ${\displaystyle n>0}$:

${\displaystyle \pi (n)\geq {\frac {n}{\varepsilon (n)\log n}}.}$

Оба доказательства представлены более подробно.^[4]

Теория графов

А помеченный график ${\displaystyle G=(V,E)}$ с ${\displaystyle n}$ узлы могут быть представлены строкой ${\displaystyle E(G)}$ из ${\displaystyle {n \choose 2}}$ биты, где каждый бит указывает на наличие (или отсутствие) края между парой узлов в этой позиции. ${\displaystyle K(G)\geq {n \choose 2}}$, а степень ${\displaystyle d}$ каждой вершины удовлетворяет

${\displaystyle |d-n/2|=O\left({\sqrt {n\log n}}\right).}$

Чтобы доказать это методом несжимаемости, если отклонение больше, мы можем сжать описание ${\displaystyle G}$ ниже ${\displaystyle K(G)}$; это дает требуемое противоречие. Эта теорема требуется в более сложном доказательстве, где аргумент несжимаемости используется несколько раз, чтобы показать, что количество немаркированных графов равно

${\displaystyle \sim {\frac {2^{n \choose 2}}{n!}}.}$^[5]

Комбинаторика

Переходный турнир это полный ориентированный граф, ${\displaystyle G=(V,E)}$; если ${\displaystyle (i,j),(j,k)\in E}$, ${\displaystyle (i,k)\in E}$. Рассмотрим множество всех переходных турниров на ${\displaystyle n}$ узлы. Поскольку турнир - это помеченный, направленный полный график, его можно закодировать строкой ${\displaystyle E(G)}$ из ${\displaystyle {n \choose 2}}$ биты, где каждый бит указывает направление границы между парой узлов в этой позиции. Используя эту кодировку, каждый транзитивный турнир содержит транзитивный субтурнир на (как минимум) ${\displaystyle v(n)}$ вершины с

${\displaystyle v(n)\leq 1+\lfloor 2\log n\rfloor .}$

Это было показано как первая проблема.^[6] Она легко решается методом несжимаемости,^[7] как и проблема взвешивания монет, количество покрывающих семейств и ожидаемые свойства; например, хотя бы часть ${\displaystyle 1-1/n}$ всех переходных турниров на ${\displaystyle n}$ вершины имеют транзитивные субтурниры не более чем на ${\displaystyle 1+2\lceil 2\log n\rceil }$ вершины. ${\displaystyle n}$ достаточно большой.

Если ряд событий независимый (в теория вероятности ) друг друга, вероятность того, что ни одно из событий не произойдет, может быть легко вычислена. Если события зависимы, проблема усложняется. Локальная лемма Ловаса^[8] Это принцип, согласно которому, если события в основном независимы друг от друга и имеют индивидуально небольшую вероятность, существует положительная вероятность того, что ни одно из них не произойдет.^[9] Это было доказано методом несжимаемости.^[10] Используя метод несжимаемости, несколько версий расширители и было показано, что существуют графы суперконцентраторов.^[11]

Топологическая комбинаторика

в Проблема треугольника Хейльбронна, бросать ${\displaystyle n}$ точки в единичном квадрате и определяют максимум минимальной площади треугольника, образованного тремя точками по всем возможным расположениям. Эта проблема была решена для небольших устройств, и было проделано много работы по асимптотическому выражению как функции ${\displaystyle n}$. Первоначальная гипотеза Хайльбронн был ${\displaystyle O(1/n^{2})}$ в начале 1950-х гг. Пол Эрдёш доказал, что эта оценка верна для ${\displaystyle n}$, простое число. Общая проблема остается нерешенной, за исключением наиболее известной нижней оценки ${\displaystyle \Omega ((\log n)/n^{2})}$ (достижимо; следовательно, Хайльбронн гипотеза не верна для общих ${\displaystyle n}$) и верхняя граница ${\displaystyle \exp(c{\sqrt {\log n}})/n^{8/7}}$ (доказано Комлосом, Пинцем и Семереди в 1982 и 1981 годах соответственно). Методом несжимаемости изучен средний случай. Было доказано, что если область слишком мала (или велика), ее можно сжать ниже колмогоровской сложности равномерно-случайной конфигурации (высокая колмогоровская сложность). Это доказывает, что для подавляющего большинства расположений (и математического ожидания) площадь наименьшего треугольника, образованного тремя из ${\displaystyle n}$ очки, брошенные равномерно и произвольно в единичном квадрате, ${\displaystyle \Theta (1/n^{3})}$. В этом случае метод несжимаемости доказывает нижнюю и верхнюю границы рассматриваемого свойства.^[12]

Вероятность

В закон повторного логарифма, то закон больших чисел и свойство повторения было показано с использованием метода несжимаемости^[13] и Закон нуля или единицы Колмогорова,^[14] с нормальные числа выражается как двоичные строки (в смысле Э. Борель ) и распределение нулей и единиц в двоичных строках высокой колмогоровской сложности.^[15]

Сложность времени машины Тьюринга

Основная машина Тьюринга, как задумано Алан Тьюринг в 1936 году состоит из памяти: ленты потенциально бесконечных ячеек, на которой может быть записан символ, и конечного элемента управления с прикрепленной головкой чтения-записи, которая сканирует ячейку на ленте. На каждом этапе головка чтения-записи может изменять символ в сканируемой ячейке и перемещать одну ячейку влево, вправо или вообще не перемещать в соответствии с инструкциями от конечного элемента управления. Машины Тьюринга с двумя символами ленты можно рассматривать для удобства, но это не существенно.

В 1968 г. Ф. К. Хенни показал, что такая машина Тьюринга требует порядка ${\displaystyle n^{2}}$ распознавать язык бинарных палиндромов в худший случай. В 1977 г. В. Дж. Пол^[2] представили доказательство несжимаемости, которое показало, что порядок ${\displaystyle n^{2}}$ время требуется в среднем случае. Для каждого целого числа ${\displaystyle n}$рассмотрите все слова такой длины. Для удобства рассмотрим слова, в которых средняя треть слова состоит из нулей. Принимающая машина Тьюринга заканчивается состоянием принятия слева (начало ленты). Вычисление данного слова машиной Тьюринга дает для каждого местоположения (границы между соседними ячейками) последовательность пересечений слева направо и справа налево, причем каждое пересечение происходит в определенном состоянии конечного управления. Все позиции в средней трети слова-кандидата имеют последовательность скрещивания длины ${\displaystyle O(n)}$ (с общим временем расчета ${\displaystyle O(n^{2})}$), либо некоторая позиция имеет последовательность пересечения ${\displaystyle o(n)}$. В последнем случае слово (если это палиндром ) можно идентифицировать по этой последовательности скрещивания.

Если другие палиндромы (оканчивающиеся на принимающее состояние слева) имеют такую ​​же последовательность пересечения, слово (состоящее из префикса до позиции задействованной последовательности пересечения) исходного палиндома соединенный с суффиксом также принимается оставшаяся длина другого палиндрома. Взяв палиндром ${\displaystyle \Omega (n)}$, то Колмогоровская сложность описанный ${\displaystyle o(n)}$ биты - противоречие.

Поскольку подавляющее большинство бинарных палиндромов имеют высокую колмогоровскую сложность, это дает нижнюю границу для среднего случая Продолжительность. Результат намного сложнее и показывает, что машины Тьюринга с ${\displaystyle k+1}$ рабочие ленты более мощные, чем ленты с ${\displaystyle k}$ рабочие ленты в реальное время (здесь один символ на шаг).^[3]

В 1984 г. В. Маасс^[16] и М. Ли и П. М. Б. Витаньи ^[17] показали, что моделирование двух рабочих лент одной рабочей лентой машины Тьюринга требует ${\displaystyle \Theta (n^{2})}$ время детерминированно (оптимально решение 30-летнего открытая проблема ) и ${\displaystyle \Omega (n^{2}/(\log n\log \log n))}$ время недетерминированно ^[17] (в,^[16] это ${\displaystyle \Omega (n^{2}/(\log ^{2}n\log \log n))}$. Больше результатов относительно лент, стеки и очереди, детерминированно и недетерминированно,^[17] были доказаны методом несжимаемости.^[4]

Теория вычислений

Heapsort это метод сортировки, изобретенный Дж. У. Дж. Уильямсом и усовершенствованный Р. В. Флойд, который всегда работает ${\displaystyle O(n\log n)}$ время. Сомнительно, лучше ли метод Флойда, чем метод Уильямса, в среднем, хотя в худшем случае он лучше. Методом несжимаемости было показано^[4] этот метод Уильямса работает в среднем в ${\displaystyle 2n\log n+O(n)}$ времени, а метод Флойда работает в среднем за ${\displaystyle n\log n+O(n)}$ время. Доказательство было предложено Ян Манро.

Shellsort, обнаруженный Дональд Шелл в 1959 г. сортировка сравнения который разделяет список для сортировки на подсписки и сортирует их отдельно. Затем отсортированные подсписки объединяются, восстанавливая частично отсортированный список. Этот процесс повторяется несколько раз (количество проходов). Сложность анализа сложности процесса сортировки в том, что она зависит от количества ${\displaystyle n}$ ключей, подлежащих сортировке, по количеству ${\displaystyle p}$ количества проходов и приращений, определяющих рассеяние в каждом проходе; Подсписок - это список ключей, которые являются параметрами приращения отдельно. Хотя этот метод сортировки вдохновил большое количество работ, был установлен только худший случай. Для среднего времени работы только лучший случай двухпроходной сортировки Shellsort.^[18] и верхняя граница ${\displaystyle O(n^{23/15})}$ ^[19] для определенной последовательности приращения для трехпроходной сортировки Shellsort. Общая нижняя граница в среднем ${\displaystyle p}$-pass Shellsort был дан^[20] что было первым шагом вперед в решении этой проблемы за четыре десятилетия. При каждом проходе сортировка сравнения перемещает ключ в другое место на определенное расстояние (длину пути). Все эти длины пути равны логарифмически закодированный по длине в правильном порядке (проходов и ключей). Это позволяет реконструировать несортированный список из отсортированного списка. Если несортированный список является несжимаемым (или почти несжимаемым), поскольку отсортированный список имеет близкую к нулю колмогоровскую сложность (а длины путей вместе дают определенную длину кода), сумма должна быть по крайней мере такой же большой, как колмогоровская сложность исходного списка. . Сумма длин пути соответствует времени работы, и время работы ограничено снизу в этом аргументе на ${\displaystyle \Omega (pn^{1+1/p})}$. Это было улучшено в ^[21] к нижней границе

${\displaystyle \Omega \left(n\sum _{k=1}^{p}h_{k-1}/h_{k}\right)}$

куда ${\displaystyle h_{0}=n}$. Это означает, например, нижнюю оценку Цзян-Ли-Витаньи для всех ${\displaystyle p}$-проходить последовательности приращения и улучшает эту нижнюю границу для определенных последовательностей приращения; верхняя граница Янсона-Кнута соответствует нижней границе для используемой последовательности приращения, показывая, что трехпроходная сортировка Shell для этой последовательности приращения ${\displaystyle \Theta (n^{23/15})}$ инверсии.

Другой пример выглядит следующим образом. ${\displaystyle n,r,s}$ натуральные числа и ${\displaystyle 2\log n\leq r,s\leq n/4}$, было показано, что для каждого ${\displaystyle n}$ Существует Булево ${\displaystyle n\times n}$ матрица; каждый ${\displaystyle s\times (n-r)}$ подматрица имеет классифицировать по меньшей мере ${\displaystyle n/2}$ методом несжимаемости.

Логика

В соответствии с Первая теорема Гёделя о неполноте, в каждой формальной системе с вычислимо перечислимыми теоремами (или доказательствами), достаточно сильными, чтобы содержать Арифметика Пеано, есть верные (но недоказуемые) утверждения или теоремы. Это доказано методом несжимаемости; каждая формальная система ${\displaystyle F}$ можно описать конечным образом (например, в ${\displaystyle f}$ биты). В такой формальной системе мы можем выразить ${\displaystyle K(x)\geq |x|}$ поскольку он содержит арифметику. Данный ${\displaystyle F}$ и натуральное число ${\displaystyle n\gg f}$, мы можем найти исчерпывающее доказательство того, что некоторая строка ${\displaystyle y}$ длины ${\displaystyle n}$ удовлетворяет ${\displaystyle K(y)\geq n}$. Таким образом мы получаем первую такую ​​строку; ${\displaystyle K(y)\leq \log n+f}$: противоречие.^[22]

Сравнение с другими методами

Хотя вероятностный метод обычно показывает существование объекта с определенным свойством в классе, метод несжимаемости имеет тенденцию показать, что подавляющее большинство объектов в классе (среднее или ожидаемое) обладают этим свойством. Иногда легко превратить вероятностное доказательство в доказательство несжимаемости или наоборот. В некоторых случаях трудно или невозможно превратить доказательство по несжимаемости в вероятностное (или счетное доказательство). Практически во всех упомянутых выше случаях временной сложности машины Тьюринга метод несжимаемости решал проблемы, которые были открытыми в течение десятилетий; никаких других доказательств не известно. Иногда доказательство по несжимаемости можно превратить в доказательство счетом, как это произошло в случае общей нижней оценки времени работы Shellsort.^[20]

Рекомендации

1. Колмогоров А. Н. Три подхода к определению понятия «количество информации». Пробл. Передачи Инф., 1:1 (1965), 3–11
2. W. J. Paul, "Сложность Колмогорова и нижние оценки", стр. 325–333 в: L. Budach Ed., Proc. 2-й Int. Конф. Фонд. Comput. Теория, 1979.
3. У. Дж. Пол, Дж. И. Сейферас, Дж. Саймон, "Теоретико-информационный подход к ограничению времени для онлайн-вычислений" (предварительная версия), Proc. 12-й симпозиум ACM. Теория вычислений (STOC), 357–367, 1980.^{[постоянная мертвая ссылка ]}
4. М. Ли, П. М. Б. Витаньи, Введение в колмогоровскую сложность и ее приложения, Springer, 1993, 1997, 2008, Глава 6.
5. Х. М. Бурман, М. Ли, Дж. Т. Тромп, П. М. Б. Витаньи, "Колмогоровские случайные графы и метод несжимаемости", SIAM J. Comput., 29:2(1999), 590–599.
6. П. Эрдош, Дж. Спенсер, Вероятностные методы в комбинаторике, Academic Press, 1974.
7. М. Ли, П. М. Б. Витаньи, "Аргументы колмогоровской сложности в комбинаторике", J. Комбинаторная теория, Series A, 66: 2 (1994), 226–236.
8. П. Эрдеш, Л. Ловас, «Проблемы и результаты о 3-хроматических гиперграфах и некоторые связанные вопросы», в A. Hajnal, R. Rado, and V. T. Sós, eds. Бесконечные и конечные множества (Полу Эрдёшу в день его 60-летия). Северная Голландия. С. 609–627.
9. Р. А. Мозер, Г. Тардос, "Конструктивное доказательство общей локальной леммы Ловаса", Журнал ACM (JACM), 2:57(2010), 11.
10. Л. Фортноу, "Доказательство колмогоровской сложности локальной леммы Ловаса", Журнал вычислительной сложности, 2 июня 2009 г.
11. У. Шонинг, "Конструирование расширителей и суперконцентраторов с использованием колмогоровской сложности", Случайные структуры и алгоритмы, 17:1(2000), 64–77.
12. Т. Цзян, М. Ли, П. М. Б. Витаньи, "Средняя площадь треугольников типа Хейльбронна", Случайные структуры и алгоритмы, 20:2(2002), 206–219.
13. В. Г. Вовк, "Закон повторного логарифма для случайных колмогоровских или хаотических последовательностей", Теория вероятн. Appl. 3:32(1988), 413–426.
14. М. Зиманд, "Закон колмогоровской сложности high-low, эквивалентный закону 0–1", Сообщить. Процесс. Буквы, 57:2(1996), 59–84.
15. М. Ли, П. М. Б. Витаньи, "Статистические свойства конечных последовательностей высокой колмогоровской сложности", Математическая теория систем, 27(1994), 365–376.
16. W. Maass, "Комбинаторные аргументы нижней границы для детерминированных и недетерминированных машин Тьюринга", Пер. Амер. Математика. Soc. 292 (1985), 675–693.
17. М. Ли, П. М. Б. Витани, «Лента против очереди и стопок: нижние границы», Информация и вычисления, 78:1(1988), 56–85.
18. Д. Э. Кнут, Сортировка и поиск (Том 3 Искусство программирования), 2-е изд. Эддисон-Уэсли, 1998, стр 83–95.
19. С. Янсон, Д. Э. Кнут, "Shellsort с тремя приращениями", Алгоритмы случайных структур 10:1–2(1997), 125–142.
20. Т. Цзян, М. Ли, П. М. Б. Витаньи, "Нижняя оценка средней сложности Shellsort", Журнал ACM (JACM), 47:5(2000) 905–911.
21. P.M.B. Витани (2018), О средней сложности Shellsort, случайных структур и алгоритмов, 52: 2, 354--363
22. Г. Дж. Чайтин, Алгоритмическая теория информации, Издательство Кембриджского университета, 1977.