Вывод полиномиальных представлений для некоторых вычислительных задач

Введение 3
Постановка задачи 7
1. Обозначения 8
2. Обзорный раздел по предметной области 9
2.1. Тонкие сведения на время работы алгоритмов 9
2.2. Задача выполнимости и гипотеза SETH 10
2.3. Нижние оценки на схемную сложность 11
2.4. Полиномиальные представления 13
2.5. Задача нахождения арифметической схемы минимального
размера 14
2.6. Разбиение дерева на сбалансированные поддеревья 15
2.7. Задачи, которые рассматриваются в работе 16
3. Основной результат 18
3.1. Полиномиальные представления для NP-трудных задач ... 18
3.2. Полиномиальные представления для полиномиальных задач 29
Заключение 36
Список литературы 37

Купить

Доказательство нижних оценок на время работы является центральным направлением теории сложности алгоритмов. К сожалению, это удаётся сделать только в ограниченных моделях вычислений, в общем случае же эта проблема является чрезвычайно сложной. Чтобы как-то совладать со сложностью задачи, была придумана довольно естественная и в то же время мощная идея: доказательство условных нижних оценок. В основу условных нижних оценок входят так называемые тонкие сведения на время работы алгоритмов: сведение (A,p(n)) < (B,q(n)) означает, что из существования алгоритма для задачи B, который работает „быстрее“ q(n), следует существование более „быстрого“, чем p(n), алгоритма для A. Тривиальным примером тонкого сведения является полиномиальное сведение по Карпу: если NP-трудная задача A сводится к задаче B за полиномиальное время, то в предположении P = NP задача B не имеет алгоритма с полиномиальным временем работы. Есть довольно большое количество гипотез, которые позволяют доказывать более сильные нижние оценки, например (далее предполагается, что утверждения верны для любого е > 0):
• Задача выполнимости булевых формул (k-SAT) требует время работы cn для некоторого неявного c > 1 [25], [26];
• 3-Сумма (3-SUM) не решается за время п2-е [15], [23];
• Задача об ортогональных векторах (OV) не решается за время п2-е [40];
• Задача о покрытии множествами (Set Cover) не решается за время (2 - е)п [11].
• Задача о нахождении попарных кратчайшихрасстояний(APSP} не решается за время п3-е [38].
Одна из самых известных гипотез называется гипотезой сильного экспоненциального времени (SETH). Она утверждает, что для любого е > 0 существует такое к, что задача k-SAT не решается за время (2 — г)п. Тонкие сведения, из которых следуют нижние оценки под гипотезой SETH, называются SETH-сведениями. На данный момент показано довольно много SETH-сведений для различных задач.
Однако построение SETH-сведений для ряда задач является открытой проблемой. В последнем десятилетии были найдены несколько барьеров, которые объясняют сложность построения таких сведений. Первый барьер основан на следующей идее. Пусть A G DTIME[T1], B G DTIME[T2] и A тонко сводится к B таким образом, что если B G DTIME[T21—е] для некоторого г > 0, то A G DTIME[T11—6] для некоторого 5 = 5(e). Тогда если B G (N П coN)TIME[T21—е], то A G (N П coN)TIME[T11—6] [14, Лемма 3.5]. Таким образом, чтобы исключить сведение (A, T1) < (B, T2), достаточно показать, что B G (N П coN)TIME[T2 — е] для некоторого г > 0, а A маловероятно принадлежит (N П coN)TIME[T11—6] для любого 5 > 0. Если в качестве A взять задачу выполнимости булевых формул - k-SAT - то можно показать барьеры для SETH-сведений. Довольно естественным шагом является введение гипотезы NSETH (сильная гипотеза недетерминированного экспоненциального времени), которая гласит, что k-SAT G coNTIME[(2 — e)n] для любого г > 0. Оказывается, опровержение NSETH ведет к сильным нижним оценкам на схемную сложность: если NSETH неверна, то класс ENP требует параллельно-последовательные булевы схемы размера w(n) [14, Теорема 4.1]. Таким образом, существование SETH-сведений к ряду задач показать не проще, чем доказать сильные нижние оценки на схемную сложность. В предположении NSETH не существует детерминированных SETH-сведений для следующих задач [14, Теорема 5.3] (далее предполагается, что утверждения верны для всех г > 0; T(n) - время работы, для которого показываем несводимость):
• Задача о максимальном потоке (MAXFLOW) с T(n) = n1+e;
• Задача об ударяющем множестве (HITTING SET) с T(n) = n1+e;
• 3-Сумма с T(n) = n1-5+e;
• Задача о нахождении попарных кратчайших расстояний с T (n) =
n2+ +e, где ш - наилучшая константа алгоритма произведения матриц.
Совсем недавно был получен ещё один барьер, который показывает сложность доказательства нижних оценок вида Ап (или Ак для параметра к) для явных с > 1 в предположении SETH [6]. Оказывается, если некоторая NP-трудная задача допускает представление в виде полинома особого вида, то для неё вряд ли существует Ап^ЕТН-сведение. Грубо говоря, этот полином должен обладать следующими свойствами:
• deg(P) = d для некоторой константы d;
• P содержит не более О(2п/0) переменных для некоторой константы 0;
• Каждая переменная может быть вычислена за время О(2п/в') для некоторой константы 0';
• X yes-экземпляр задачи тогда и только тогда, когда P(ф(Х)) > 0, где ф - отображение подстановки значений в переменные.
Статья [6] приводит такие представления для различных NP-трудных как непараметризованных, так и параметризованных задач, и тем самым показывается сложность доказательства нижних оценок для этих задач вида сп или ck под SETH: k-SAT, MAX-k-SAT, Гамильтонов путь, Раскраска графа, Задача о покрытии множествами, Независимое множество, Клика, Вершинное покрытие, 3d-Паросочетание, k-Путь, k-Вершинное покрытие, k-Дерево, k-Изменение кластера и другие.
В этой работе мы обобщаем результат [6] на ко(1)^ЕТН-сведения (эта запись означает, что сведение показывает нижнюю оценку kO(1) на время работы, где к - некоторый параметр) и выводим полиномиальные представления для более широкого круга задач (как NP-трудных, так и для полиномиальных). Основной результат работы представлен следующими теоремами.
Теорема 1. Пусть существует хотя бы одно из следующих сведений (А > 1):
• Аn-SETH-сведение к задаче Наименьшая общая надстрока;
• АпХЕТН-сведение к задаче Наименьшее общее разбиенее строк (п - длина строки);
log log n
Хп logn -SETH-сведение к задаче Наименьшее общее разбиение строк с константным алфавитом (Ак-SETH-сведение к задаче с парамет- ппм k — n lQglQgn )• ром k - П iog n ),
Ak-SETH-сведение к задаче k-Мотив графа, где k - размер мотива;
Тогда выполняется как минимум одно из следующих утверждений:
• Класс Enp не вычисляется семейством булевых параллельно-последовательных схем размера O(n);
• Для любой y > 1 существует явный полином константной степени, который не вычисляется арифметическими схемами размера nY.
Теорема 2. Пусть существует хотя бы одно из следующих сведений (q > 1):
• nq-SETH-сведение к задаче k-Сумма с константным k;
• (n + m)q-SETH-сведение к задаче H-Изоморфизм подграфа с константным H (kq-SETH-сведение к задаче с параметром k = n + m);
Тогда выполняется как минимум одно из следующих утверждений:
• Класс Enp не вычисляется семейством булевых параллельно-последовательных схем размера O(n);
• Для некоторой y > 1 существует явный полином константной степени, который не вычисляется арифметическими схемами размера nY.

Купить