Archive for Март 2010

Преобразование Фурье на булевом кубе

Март 27, 2010

При изучении различных свойств булевых функций нередко оказывается полезным дискретное преобразование Фурье. Давайте рассмотрим его и покажем, как с помощью него доказывается лемма о тестировании линейности.

Булева функция — это функция f \colon \{0, 1\}^n \to \{0, 1\}. Заменим 0 на 1, а 1 на -1. Получится функция f \colon \{-1, 1\}^n \to \{-1, 1\}. Заметим, что сложение по модулю 2 перейдет в умножение.

Рассмотрим гильбертово пространство функций из \{-1, 1\}^n в \mathbb{R}. Сложение и умножение на число определены естественным образом, а скалярное произведение — это \langle f, g \rangle = E_{x \in \{-1, 1\}^n}(f(x) g(x)).

Рассмотрим такой ортонормальный базис в этом пространстве: \chi_S(x) = \prod_{i \in S}x_i, где S пробегает все подмножества \{1, 2, \ldots, n\} (ортонормальность проверяется очень просто). Следовательно, каждую функцию f \colon \{-1, 1\}^n \to \mathbb{R} можно записать в виде f = \sum_S \hat{f}_S \chi_S. Числа \hat{f}_S = \langle f, \chi_S \rangle называются коэффициентами Фурье. Очевидно, что верно такое равенство: \langle f, g \rangle = \sum_S \hat{f}_S \hat{g}_S, из которого следует теорема Пифагора: \langle f, f \rangle = \sum_S \hat{f}_S^2.

Теперь вернемся к нашим булевым функциям. Заметим, что в \chi_S переходят в точности линейные функции. Также понятно, что нормы образов булевых функций всегда равны 1. Более того, если нормализованное расстояние Хемминга между функциями f и g равно 1/2 + \varepsilon, то \langle f, g \rangle = 2 \varepsilon. В частности, функция f (1/2 + \varepsilon)-близка к какой-то линейной функции тогда и только тогда, когда у нее какой-то коэффициент Фурье не меньше 2 \varepsilon.

Теперь сформулируем и докажем лемму о тестировании линейности.

Лемма (о тестировании линейности). Пусть f \colon \{0, 1\}^n \to \{0, 1\} такая, что P_{x, y \in \{0, 1\}^n} [f(x \oplus y) = f(x) \oplus f(y)] \geq 1/2 + \varepsilon. Тогда f (1/2 + \varepsilon)-близка к какой-то линейной функции.

Доказательство. Опять заменим 0 на 1, а 1 — на -1. Полученную функцию тоже обозначим f. Условие леммы можно переписать тогда как P_{x, y \in \{-1, 1\}^n} [f(x \cdot y) = f(x) f(y)] \geq 1/2 + \varepsilon, где x \cdot y — покомпонентное умножение. Это, в свою очередь, можно переписать как E_{x, y \in \{-1, 1\}^n} [f(x \cdot y) f(x) f(y)] \geq 2 \varepsilon. Теперь будем пользоваться преобразованием Фурье.

2\varepsilon \leq E_{x, y \in \{-1, 1\}^n} [f(x \cdot y) f(x) f(y)] =
= E_{x, y \in \{-1, 1\}^n}[\sum_{\alpha, \beta, \gamma} \hat{f}_{\alpha}\hat{f}_{\beta}\hat{f}_{\gamma} \chi_{\alpha}(x \cdot y) \chi_{\beta}(x) \chi_{\gamma}(y)] =
= \sum_{\alpha, \beta, \gamma} \hat{f}_{\alpha}\hat{f}_{\beta}\hat{f}_{\gamma} E_{x, y \in \{-1, 1\}^n}[\chi_{\alpha}(x \cdot y) \chi_{\beta}(x) \chi_{\gamma}(y)] =
= \sum_{\alpha} \hat{f}_{\alpha}^3 \leq \max_{\alpha} \hat{f}_{\alpha}.

Значит какой-то из коэффициентов Фурье будет довольно большим, а, значит, f (1/2 + \varepsilon)-близка к какой-то линейной функции.

Реклама

Дерандомизация

Март 20, 2010

Известно, что если в \mathrm{DTIME}(2^{O(n)}) найдется фукция, для вычисления которой необходимы схемы размера 2^{\varepsilon n}, то \mathrm{P} = \mathrm{BPP}. Только вдумайтесь: из результата о трудности следует результат о легкости.

Лемма Кенига с точки зрения эффективности

Март 19, 2010

Рассмотрим бесконечное множество слов A \subseteq \{0, 1\}^*, которое замкнуто относительно взятия префиксов. Скажем, что последовательность \omega \in \{0, 1\}^{\infty} является A-последовательностью, если каждый ее префикс лежит в A.

Утверждение (частный случай леммы Кенига). Множество A-последовательностей непусто.

Доказательство. Будем выписывать искомую \omega бит за битом. На каждом шаге будем поддерживать такой инвариант: в A найдется бесконечно много продолжений выписанного куска. Очевидно, что сначала инвариант выполнен, и на каждом шаге мы его сможем поддерживать.

Пусть теперь A разрешимо. Тогда нас будет интересовать наличие вычислимых A-последовательностей.

Теорема. Существует разрешимое A такое, что все A-последовательности невычислимы.

Доказательство. Известно, что существует частичная вычислимая функция d \colon \mathbb{N} \to \{0, 1\} такая, что для любой всюду определенной вычислимой функции f \colon \mathbb{N} \to \{0, 1\} найдется вход x такой, что d(x) определено и d(x) \ne f(x). Так как d вычислимая, то найдется программа D, которая ее вычисляет.

Теперь мы хотим определить, когда x \in A. Пусть n := |x|. Скажем, что x \in A, если для любого 1 \leq i \leq n выполняется вот что: если программа D завершается на входе i не более, чем за n шагов, то должно выполняться d(i) = x_i.

  • Понятно, что A будет разрешимым. Это видно из определения. Если нам нужно убедиться, лежит ли x в A, то нужно для всех 1 \leq i \leq |x| запустить D на |x| шагов и посмотреть на результат, если таковой будет.
  • Множество A бесконечное. Действительно, в A есть слова любой длины. Если мы хотим слово длины k, то на позицию i надо поставить d(i), если D завершается за k шагов, и 0 в противном случае.
  • Нам осталось показать, что все A-последовательности невычислимы. Пусть это не так. Тогда найдется вычислимая всюду определенная f \colon \mathbb{N} \to \{0, 1\}, задающая A-последовательность. Найдется число k такое, что d(k) определено и не равно f(k). Пусть D(k) завершается за m ходов. Тогда ясно, что слово w = f(1)f(2)\ldots f(\max(k, m)) не лежит в A. Противоречие.

Таким образом, эффективно вычислять A-последовательности в общем случае надежды нет. Но если у нас есть оракул, который решает проблему остановки, то все становится просто.

Утверждение. Для любого разрешимого A найдется 0'-вычислимая A-последовательность.

Доказательство. Очевидно повторяет доказательство первого утверждения.

Even factor

Март 14, 2010

Рассмотрим направленный граф. Будем рассматривать наборы ребер такие, что в каждую вершину входит не более одной дуги, и из каждой вершины выходит не более одной дуги. Очевидно, что такие наборы — это объединения путей и циклов. Потребуем, чтобы в наборе не было нечетных циклов. Назовем полученный объект четным фактором. Будем искать четный фактор максимального размера.

В общем случае задача NP-трудна. Поэтому будем рассматривать графы специального вида — вместе с каждым нечетным циклом граф должен содержать такой же цикл, только развернутый в другую сторону. Оказывается, что в таком графе можно за O(n^4) найти максимальный четный фактор. Алгоритм очень красивый. Очень рекомендую разобраться в нем тем, кто интересуется комбинаторной оптимизацией.

Соответствующая статья здесь: http://www.cs.elte.hu/egres/tr/egres-04-18.pdf.