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
Список литературы 12
Купить

Известно, что из верхних оценок на сложность некоторых задач можно получить нижние оценки на размер булевых схем для разных классов задач. Например, в статье [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.
Мы же покажем, что из нижних оценок на конедетерминированную сложность задач 0-1 перманент, о покрытии множества и о подсчете гамильтоновых циклов в графе следуют нижние оценки на арифметические схемы. Также приведем верхнюю оценку для задачи 0-1 перманент.
Купить