Archive for Февраль 2010

Лемма Левина

Февраль 19, 2010

Довольно красивое упражнение на лемму Кенига и локальную лемму Ловаса:

Лемма. Для любого a < 1 найдется такая последовательность битов W, что для любой ее подстроки x выполняется неравенство KS(x) \geq a |x| - O(1) (KS(x) — простая колмогоровская сложность x).

Грубо говоря, существует последовательность, у которой все достаточно длинные подстроки имеют почти максимальную сложность.

Реклама

P vs NP vs ZF

Февраль 18, 2010

Взглянул сегодня на статью Ааронсона «Is \mathrm{P} Versus \mathrm{NP} Formally Independent?». Раньше мне казалась странной мысль о том, что вопрос \mathrm{P} vs \mathrm{NP} может оказаться независимым от, скажем, \mathrm{ZF}. Но, оказывается, верен следующий факт, который заставляет задуматься:

Теорема. Существует машина Тьюринга M, которая завершает свою работу на любом входе, и для которой утверждение «\mathrm{P}^{L(M)} = \mathrm{NP}^{L(M)}» независимо от \mathrm{ZF} при условии, что \mathrm{ZF} непротиворечива.

Доказательство. Известно, что найдутся два таких вычислимых оракула A и B, что \mathrm{P}^A = \mathrm{NP}^A, но \mathrm{P}^B \ne \mathrm{NP}^B.

Занумеруем все слова x_1, x_2, \ldots и все доказательства в \mathrm{ZF} p_1, p_2, \ldots.

Скажем, что наша искомая M допускает x_k, если

  • Среди p_1, \ldots, p_k есть доказательство того, что \mathrm{P}^{L(M)} = \mathrm{NP}^{L(M)}, и x_k \in B.
  • Среди p_1, \ldots, p_k есть доказательство того, что \mathrm{P}^{L(M)} \ne \mathrm{NP}^{L(M)}, и x_k \in A.

Заметим, что мы поступили нечестно: мы используем для построения M конструкцию M. Но эта трудность легко преодолевается с помощью теоремы Клини о неподвижной точке.

Докажем теперь, что «\mathrm{P}^{L(M)} = \mathrm{NP}^{L(M)}» независимо от \mathrm{ZF} (если \mathrm{ZF} непротиворечива).

Действительно, пусть \mathrm{ZF} \vdash \mathrm{P}^{L(M)} = \mathrm{NP}^{L(M)}. Тогда, начиная с некоторого момента, L(M) совпадает с B, а, значит, \mathrm{P}^{L(M)} \ne \mathrm{NP}^{L(M)} (различие в конечном множестве слов, как несложно убедиться, не влияет на верность этого утверждения).

Симметрично разбирается случай \mathrm{ZF} \nvdash \mathrm{P}^{L(M)} = \mathrm{NP}^{L(M)}.


Отметим, что L(M) — пустой язык, но мы это не можем доказать в \mathrm{ZF}!!!

Видно также, что мы используем явное задание оракула с помощью конкретной машины Тьюринга. Однако, можно построить вычислимый оракул O такой, что «\mathrm{P}^{O} = \mathrm{NP}^{O}» независимо от \mathrm{ZF}, какой бы машиной Тьюринга мы O не задавали.

Две корневых идеи

Февраль 10, 2010

Мне бы хотелось рассказать про две идеи, в которых довольно красиво появляется квадратный корень.

1. Пусть у нас есть граф, который можно раскрасить в три цвета. Известно, что поиск трехцветной раскраски является NP-трудной задачей. Однако, можно раскрасить граф за полиномиальное время в O(\sqrt{n}) цветов. Это делается в два этапа.

На первом этапе мы избавляемся от вершин, степень которых больше \sqrt{n}. Это делается так. Рассмотрим любую такую вершину v. Рассмотрим граф, индуцированный соседями v. Он двудольный, поэтому его можно раскрасить за полиномиальное время в 2 цвета. Мы берем новые 3 цвета, красим в них v и ее соседей, а потом удаляем их из графа. Понятно, что каждый раз мы выкидываем по крайней мере \sqrt{n} вершин, а, значит, мы избавимся от вершин степени больше \sqrt{n}, использовав не более, чем 3 \sqrt{n} цветов.

Второй этап состоит в покраске полученного графа со степенями не больше, чем \sqrt{n}. Это делается простым жадным алгоритмом. Перебираем вершины графа по очереди и красим очередную вершину в наименьший возможный цвет. Понятно, что мы потратим не больше, чем \sqrt{n} + 1 цветов.

2. Пусть у нас есть сервер, на котором хранится база данных A, состоящая из n битов, и клиент. Клиент хочет получить из базы данных бит с номером 1 \leq i \leq n так, чтобы у сервера не оказалось никакой информации об i. Самое простое решение — попросить у сервера всю базу данных. Несложно понять, что в случае одного сервера это лучшее, что мы можем сделать — обойтись пересылкой меньше чем n битов не представляется возможным.

Пусть у нас теперь два сервера, которые не общаются друг с другом. Оказывается, что в этом случае можно предложить протокол, в процессе которого передается O(\sqrt{n}) битов.

Сначала построим неоптимальную версию алгоритма. Клиент генерирует случайное подмножество S \subseteq \{1, 2, \ldots, n\}, передает первому серверу S, а второму S \oplus i. Сервер в ответ на множество Q присылает один бит — \bigoplus_{k \in Q}A_k. Получив от серверов по биту, клиент вычисляет их xor и получает искомый бит A_i.

Теперь покажем, как уменьшить количество передаваемой информации до O(\sqrt{n}). Разобьем A на \sqrt{n} кусков по \sqrt{n} бит каждый. Пусть i-й бит находится в куске p под номером q. Тогда мы с помощью описанного протокола можем, к примеру, получить бит с номером q из первого куска за O(\sqrt{n}) пересылок битов. Но если сервера сразу будет посылать ответы для всех кусков, то мы найдем среди них наш i-й бит. Таким образом, сначала мы посылаем серверам \sqrt{n} битов, а потом они возвращают нам по \sqrt{n} битов.

Разные виды коммуникационной сложности

Февраль 9, 2010

Однажды, в начале 90х, на мехмате МГУ состоялся семинар по относительно новой тогда коммуникационной сложности. На нем докладчик сформулировал открытую проблему: верно ли, что квадратичный зазор между детерминированной и недетерминированной сложностями действительно достижим? Через 5 минут один из участников семинара решил эту проблему. Он опирался на следующий факт:

Теорема. Рассмотрим k-элементные подмножества \{1, 2, \ldots, n\}. Рассмотрим квадратную матрицу размера C_n^k на C_n^k. В клетке (i, j) стоит единица, если соответствующие множества не пересекаются, и ноль — в противном случае. Утверждается, что если k \leq n / 2, то матрица имеет полный ранг.

Это был Александр Разборов.

Красивый результат из теории графов

Февраль 8, 2010

Как мне кажется, формулировку следующей теоремы стоит знать тем, кто интересуется теорией графов.

(more…)