Метод несжимаемости

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

История

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

Одним из первых применений метода несжимаемости с колмогоровской сложностью в теории вычислений было доказательство того, что время работы одноленточной машины Тьюринга квадратично для принятия палиндромного языка, а алгоритмы сортировки требуют как минимум $n\log n$ время сортировать $n$ предметы. Одна из первых влиятельных статей, использующих метод несжимаемости, была опубликована в 1980 году. Этот метод был применен к ряду областей, а его название было придумано в учебнике.

Приложения

Теория чисел

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

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

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

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

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

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

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

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

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

$\sim {\frac {2^{n \choose 2}}{n!}}.$

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

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

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

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

Если ряд событий независимы (в теории вероятностей ) друг от друга, вероятность того, что ни одно из событий не произойдет, можно легко вычислить. Если события зависимы, задача усложняется. Локальная лемма Ловаса Это принцип, согласно которому, если события в основном независимы друг от друга и имеют индивидуально малую вероятность, существует положительная вероятность того, что ни одно из них не произойдет. Это было доказано методом несжимаемости. С помощью метода несжимаемости экспандеров и суперконцентраторов. было показано существование нескольких вариантов графов-

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

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

Вероятность

закона повторного логарифма , закона больших чисел и свойства рекуррентности. С помощью метода несжимаемости показано выполнение и закон нуля-единицы Колмогорова , с нормальными числами, выраженными в виде двоичных строк (в смысле Э. Бореля ) и распределением нулей и единиц в двоичных строках высокой колмогоровской сложности.

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

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

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

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

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

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

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

Пирамидальная сортировка — это метод сортировки, изобретенный Дж. У. Дж. Уильямсом и усовершенствованный Р. У. Флойдом , который всегда работает в $O(n\log n)$ время. Сомнительно, что метод Флойда в среднем лучше, чем метод Уильямса, хотя в худшем случае он лучше. С помощью метода несжимаемости было показано что метод Уильямса работает в среднем $2n\log n+O(n)$ время и метод Флойда работает в среднем за $n\log n+O(n)$ время. Доказательство было предложено Яном Манро .

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

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

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

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

Логика

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

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

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