1 Введение 3
2 Определения и используемые результаты 3
3 Формулировка основных результатов 4
4 Верхняя оценка для задачи 0-1 перманент 4
4.1 Необходимые формулы 5
4.2 Описание алгоритма 5
4.3 Анализ 6
5 Построение недетерминированного алгоритма с помощью арифметических
схем 6
6 Построение сведений к многочленам 7
6.1 Задача о покрытии множества 7
6.2 Задача о подсчете гамильтоновых циклов 9
6.3 Задача 0-1 перманент 10
7 Список литературы 11
Известно, что из верхних оценок на сложность некоторых задач можно получить нижние оценки на размер булевых схем для разных классов задач. Например, в статье [1] было показано, что из верхних оценок для задачи Circuit SAT следует, что NEXP С P/poly, то есть, в классе NEXP существует задача, для которой не существует булевых схем полиномиального размера. Далее в статье [2] было показано, что улучшение известной константы с, для которой 3-SAT решается за время cn, влечет существование задачи из класса ENP, булевы схемы для которой должны содержать не менее 3n невходных гейтов.
Также в статье [3] была введена следующая гипотеза:
Гипотеза 1. Nondeterministic Strong Exponential Time Hypothesis (NSETH) Для любого e > 0 существует такое k, что k-TAUT ^ NTIME(2ra(1-€)), где k-TAUT - язык формул, являющихся тавтологиями в дизъюнктивной нормальной форме, в которых в каждом клозе ровно k литералов.
В [3] было показано, что отрицание гипотезы 1 влечет нижние оценки на несколько классов булевых схем. Если же гипотеза 1 верна, то к задачам, для которых существуют достаточно быстрые как недетерминированные, так и конедетерминированные алгоритмы, не существует эффективных fine-grained сведений от задачи SAT.
Мы же покажем, что из нижних оценок на конедетерминированную сложность задач 01 перманент, о покрытии множества и о подсчете гамильтоновых циклов в графе следуют нижние оценки на арифметические схемы. Также приведем верхнюю оценку для задачи 0-1 перманент.
Определим задачу, которая потребуется нам в качестве промежуточной.
Определение 8. Задача Измененный 0-1 перманент: дано число n, двудольный граф с долями размера k Е [n] и n и число m Е [k]. Посчитать количество наборов ребер таких, что каждая из первых m вершин левой доли и каждая вершина правой доли графа смежна ровно с одним ребром из набора.
Лемма 9. Для любого a Е (0,1) задача 0-1 перманент сводится к 2(1-а)га инстансам задачи Измененный 0-1 перманент с параметрами n, an за время ф*(2(1-а)га).
Доказательство. Задача 0-1 перманент эквивалентна вычислению количества совершенных паросочетаний в двудольном графе на 2п вершинах. Пусть B - множество наборов ребер таких, что каждая из первых an вершин левой доли и каждая из вершин правой доли графа смежна ровно с одним ребром из набора. Пусть Ai - подмножество B, состоящее из наборов, в котором хотя бы одно ребро смежно с вершиной левой доли с номером i. Тогда множество решений нашей задачи - |Д Ai. По формуле включений-исключений ie[an+1,n]
I A Ai| = (—1)|X||B ( U Aj)|. Для каждого из 2(1-а)га вариантов множества
ie[an+1,n] XC[on+1,n] jeX
X достаточно вычислить ответ на задачу Измененный 0-1 перманент для графа из исходной задачи без вершин левой доли с номерами из множества X с параметрами n, an. □
Лемма 10. Для любого 1 < О Е N задача Измененный 0-1 перманент сводится к вычислению значения многочлена степени О от Ф*((™)) переменных, и подставляемые вместо переменных значения можно вычислить суммарно за время O*((m) 2m). Все коэффициенты этого многочлена можно вычислить за время O* (Отнв).
Доказательство. Введем множество переменных X = {xs,i,r|S С [m], |S| = у, 1 < l < r < n}, в которые подставим следующие значения: xs,i,r - количество способов выбрать ровно по одному ребру, смежному с каждой вершиной правой доли с номерами с l по r и только с ними, так, чтобы с каждой вершиной левой доли с номерами из множества S было смежно ровно одно из выбранных ребер, а с остальными вершинами левой доли с номерами из [m] выбранные ребра не были смежны. При этом, если 1 = 1, ребро, смежное с вершиной правой доли с номером l, должно быть смежно с вершиной левой доли с номером из S.
Значение каждой переменной можно вычислить за время O*(2m) методом динамического программирования, положив {dps',i,r S' С S, 1 < l < r < n}, где dps',i,r определено так же, как xs',i,r (только без ограничения на размер Sz).
Рассмотрим некоторый подходящий нам набор ребер. Разобьем вершины правой доли графа на «отрезки» из вершин с идущими подряд номерами так, что вершины каждого «отрезка» соединены ребрами из набора ровно с у вершинами левой доли с номерами из [m]. Первый «отрезок» будет начинаться с вершины с номером 1, а каждый следующий - с вершины vi, соединенной ребром из набора с вершиной левой доли с номером из [m]. Пусть Si - множество номеров вершин левой доли из [m], соединенных ребрами из набора с вершинами i-го «отрезка».
Тогда ответ на задачу Измененный 0-1 перманент равен P (X)
Помощь студентам и аспирантам в выполнении работ от наших партнеров
