Search
Семинар 21 мая 1999 года
Пятница, 21 мая, комната 106. Начало в 18:00.
21 мая.
Э.Гирш. Доклад по статье Impagliazzo, Paturi, Zane "Which Problems Have Strongly Exponential Complexity?"
Доклад посвящен вопросу "можно ли решить NP-полную задачу за время 2^{epsilon n}" (для произвольного малого epsilon). Вводятся специальные редукции и с помощью результатов о полноте относительно этих редукций доказывается, что вопрос этот одинаково решается для многих задач (k-выполнимость, k-раскрашиваемость, клика...) Основная лемма -- такая редукция k-выполнимости с параметром "кол-во переменных" к k-выполнимости с параметром "кол-во дизъюнкций" (именно в эту сторону).
Имеется также несколько побочных результатов, но нет гарантии, что на них хватит времени в полном объеме.
---
Keywords: NP-complete problems, SAT, time complexity, Boolean circuits, pseudorandom generators.
Abstract. For several NP-complete problems (SAT, k-SAT, 3-Coloring), there have been a progression of better but still exponential algorithms (e.g., 3-SAT: 2^N, 1.8^N, 1.62^N, 1.57^N, 1.49^N, 1.37^N...). An intriguing question is whether for each positive epsilon there is a 2^{epsilon N}-time algorithm for each of these problems (*). The authors introduce a generalized reduction SERF which preserves sub-exponential complexity. One of the consequences of the results of the paper is that (*) is equivalent for k-SAT, k-Colorability, k-Set Cover, Independent Set, Clique, Vertex Cover (these problems are SERF-complete for the class SNP of search problems expressible by second order existential formulas whose first order part is universal).
The main technical lemma is an algorithm that, for any positive epsilon, represents an arbitrary k-CNF formula as a disjunction of 2^{epsilon n} k-CNF formulas of linear size (i.e., each consists of O(n) clauses).
By-products. 1. With high probability, degree 2 random GF(2) polynomials require strongly exponential size for \Sigma^3_k circuits for k=o(log log n). 2. Thus there is a pseudorandom generator with O(n^2) bits of advice that maps n bits into a large number of bits so that computing parity is hard for that curcuits.