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

Доказательство нижних оценок на время работы является центральным направлением теории сложности алгоритмов. К сожалению, это удаётся сделать только в ограниченных моделях вычислений, в общем случае же эта проблема является чрезвычайно сложной. Чтобы как-то совладать со сложностью задачи, была придумана довольно естественная и в то же время мощная идея: доказательство условных нижних оценок. В основу условных нижних оценок входят так называемые тонкие сведения на время работы алгоритмов: сведение (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.

Купить

Данная работа является продолжением [6], она показывает барьеры SETH-сводимости для более широкого круга как NP-трудных, так и полиномиальных задач: Наименьшая общая надстрока, Наименьшее общее разбиение строк, Наименьшее общее разбиение строк с константным алфавитом, k-Мотив графа, k-Сумма с константным k, H-Изоморфизм графа с константным H. В качестве заключения приведем некоторые открытые проблемы, которые возникают в области тонких оценок и связаны с темой работы.
Первая проблема - найти полиномиальное представление сложности 1п1/ для любого 0 > 1 для Задачи об ударяющем множества. В [11] показано, что Задача об ударяющем множества 2"-SETI I-трудная, значит существование такого полиномиального представления автоматически давало бы нижние оценки на схемную сложность. Вторая, не менее важная проблема, найти барьеры для несводимости в предположении других гипотез: 3-SUM, APSP, SCH и др. Возможно ли использовать для этого похожую машинерию, которая была развита в [14] и [6]?
Купить