On generic NP-completeness of the Boolean satisfiability problem.pdf Введение Важнейшим понятием классической теории сложности вычислений является понятие полиномиальной сводимости алгоритмических проблем. С его помощью можно сравнивать проблемы по вычислительной сложности и развивать богатую теорию NP-полноты [1]. В работе [2] введено понятие полиномиальной сводимости и NP-полноты в среднем. В [3] приведены примеры алгоритмических проблем, которые являются NP-полными в среднем. При анализе вычислительной сложности проблемы в среднем изучается математическое ожидание времени работы алгоритма для всех входов данного размера. В рамках генерического подхода [4] алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения практики алгоритмы, быстро решающие проблему на генерическом множестве, так же хороши, как и быстрые алгоритмы для всех входов. Классическим примером такого алгоритма является симплекс-метод - он за полиномиальное время решает задачу линейного программирования для большинства входных данных, но имеет экспоненциальную сложность в худшем случае. Более того, может так оказаться, что проблема трудноразрешима или вообще неразрешима в классическом смысле, но легкоразрешима на генерическом множестве. Для многих классических NP-полных проблем существуют полиномиальные генерические алгоритмы [5]. В данной работе вводится понятие генерической полиномиальной сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы за полиномиальное время для почти всех входов при условии равенства классов P = BPP, где класс BPP состоит из проблем, разрешимых за полиномиальное время на вероятностных машинах Тьюринга. В работе [6] доказано, что это равенство следует из весьма правдоподобных гипотез о вычислительной сложности некоторых трудных проблем. Далее в работе доказывается, что проблема выполнимости булевых формул [7] является полной относительно генерической полиномиальной сводимости в генерическом аналоге класса NP. 1. Генерические алгоритмы Пусть I - некоторое множество. Функция size : I ^ N называется функцией размера, если для любого n G N множество = {x G I : size(x) = n} конечно. Например, если I = Е* -множество слов над конечным алфавитом Е, то функцией размера будет функция, определённая для любого слова w как его длина |w|. Для множества натуральных чисел N функция размера сопоставляет любому натуральному числу длину его двоичной записи. Как обычно делается в теории вычислимости, будем под алгоритмическими проблемами понимать проблемы распознавания подмножеств из некоторого множества входов с определённой на нем функцией длины. Для подмножества S С I определим последовательность Pn(S) = ^, n =1, 2, 3,..., 1 ^га1 где Sn = S П /га - множество входов из S размера n. Заметим, что pn(S) -это вероятность попасть в S при случайной и равновероятной генерации входов из In. Асимптотической плотностью S назовем предел (если он существует) p(S) = lim pn(S). Множество S называется генерическим, если p(S) = 1, и пренебрежимым, если p(S) = 0. Очевидно, что S генерическое тогда и только тогда, когда его дополнение I \ S пренебрежимо. Следуя [4], назовём множество S строго пренебрежимым, если последовательность pn(S) экспоненциально быстро сходится к нулю, т.е. существуют константы а, 0 < а < 1, и C > 0, такие, что для любого n Pn(S) < Can. Теперь S называется строго генерическим, если его дополнение I \ S строго пренебрежимо. Алгоритм A с множеством входов I и множеством выходов J U {?} (? Е J) называется (строго) генерическим, если 1) A останавливается на всех входах из I; 2) множество {x Е I : A(x) = ?} является (строго) генерическим. Аналогично определяется понятие вероятностного генерического алгоритма. Генерический алгоритм A вычисляет функцию f : I ^ J, если (A(x) = y Е J) ^ (f (x) = y) для всех x Е I. Ситуация A(x) = ? означает, что A не может вычислить функцию f на аргументе x. Но условие 2 гарантирует, что A корректно вычисляет f на почти всех входах (входах из генерического множества). Множество S С I называется (строго) генерически разрешимым за полиномиальное время, если существует (строго) генери-ческий полиномиальный алгоритм, вычисляющий его характеристическую функцию. Различие между генерически разрешимыми проблемами и строго генерически разрешимыми проблемами поясняется в работе [8]. 2. Генерическая полиномиальная сводимость Пусть I, J - некоторые множества входов с определёнными на них функциями размера, P(J) -множество всех подмножеств J. Множество A С I генерически полиномиально сводится к множеству B С J (обозначается A ^GenP B), если существуют вероятностный полиномиальный алгоритм R : I х N ^ P(J) U {?,!} , полином p(n), полином q(n) степени больше 2 и константа C > 0, такие, что: 1) для всех x Е I либо (Vn R(x,n) = ?), либо для всех n ^ q(k), где k = size(x), выполнены следующие условия: а) Vy Е R(x,n) (y = ! ^ size(y) = n); б) все элементы в R(x, n) \ {!} выдаются алгоритмом R равновероятно; в) вероятность получить ответ ! в R(x,n) не больше 2-Ck; ) |R(x,n)| > 1 ) |Jn| (p(n))k; д) x Е A ^ R(x,n) С B; е) x Е A ^ r(x, n) С J \ B; 2) множество {x Е I : Vn (R(x,n) = ?)} строго пренебрежимо. Рассмотрим подробнее каждое из свойств данного определения. Помимо элементов множества J, алгоритм R может выдавать два особых выхода: ? - неопределённый ответ и ! - неудачная генерация. Вероятностный полиномиальный алгоритм R (если его выход не равен ?) каждому элементу x множества входов I проблемы A и каждому размеру n ^ q(size(x)) сопоставляет достаточно большое подмножество (свойство 1, г) R(x, n) входов J проблемы B размера n (свойство 1, а). При этом каждый элемент из R(x, n), за исключением элемента !, генерируется равновероятно (свойство 1, б). Вероятность получить неудачно сгенерированный выход ! экспонециально мала (свойство 1, в). Свойства 1, д и 1, е гарантируют, что это подмножество полностью попадает в B, если x Е A, и полностью лежит вне B для x Е A. Свойство 2 говорит о том, что алгоритм R лишь для пренебрежимого множества входов из I может всегда выдавать неопределённый ответ. Теорема 1. Если A ^oenP B и B строго генерически разрешимо за полиномиальное время, то для A существует полиномиальный вероятностный алгоритм, распознающий A на некотором полиномиальном строго генерическом множестве. Таким образом, при условии P = BPP множество A строго генерически разрешимо за полиномиальное время. Доказательство. Пусть R - полиномиальный вероятностный алгоритм, осуществляющий генерическую полиномиальную сводимость A ^cenp B; B - строго ге-нерический полиномиальный алгоритм, вычисляющий характеристическую функцию множества B; q(n) -многочлен из определения сводимости A ^oenp B. Вероятностный генерический алгоритм A, вычисляющий характеристическую функцию множества A, работает на входе x размера n следующим образом: 1) запустить алгоритм R(x,q(n)), который выдаёт ответ у; 2) если у = ?, выдать ?; 3) если у = !, выдать НЕТ; 4) иначе запустить алгоритм B на у Е J; 5) если B(y) = ?, выдать НЕТ; 6) иначе выдать ответ B(y). Очевидно, что этот вероятностный алгоритм полиномиален. Кроме того, неопределённый ответ он выдаёт на строго генерическом множестве - это следует из свойства 2 определения генерической полиномиальной сводимости. Заметим, что неправильный ответ алгоритм может выдать на шагах 3 и 5. Докажем, что вероятность этого меньше 1/2. Для шага 3 вероятность меньше 2-Cn по свойству 1, в из определения сводимости - меньше 1/4 при достаточно большом n. Для шага 5 она не больше |{у Е J : B(y) = ?}q(n)1 _ |{У Е J : B(y) = ? }q(n)1 1 Jq(n)1 |R(x,q(n))| I Jq(n) | |R(x, q(n))| ' Напомним, что индекс q(n) внизу означает, что мы рассматриваем в соответствующих множествах только элементы размера q(n). Так как алгоритм B строго генерический, то существует константа а > 0, такая, что |{у Е J : B(y) = ?}q(n)| < 1 |J | q(n) 2aq(n) ' Из свойства 1, г определения сводимости следует, что существует полином p(n), такой, что для любого n Iq(n^, < p(q(n))n = 2nМр(*(п))). |R(x,q(n))| Получаем оценку сверху для вероятности выдачи ответа на шаге 5 2n log(p(q(n))) \ \ \ _ = 2a log(P( 0. ■ 3. Генерическая NP-полнота проблемы выполнимости булевых формул В работе [8] введено представление булевых формул с помощью бинарных деревьев. Это представление более компактно и практично, чем классическое представление булевых формул с помощью таблиц истинности, когда размер таблицы растёт экспоненциально с ростом числа переменных. Представление формул с помощью бинарных деревьев часто используется в программировании различных приложений, связанных с символьными вычислениями. Кроме того, оно удобно для различного рода подсчётов. Напомним вкратце, в чём заключается этот способ представления. Булевой формуле ф в базисе {V, Л, -} сопоставляется бинарное дерево Тф, внутренние вершины которого помечены символами V и Л, а листья - переменными или их отрицаниями. С бинарным деревом Тф, имеющим n листьев, связывается множество переменных {x1,... , xn} так, что каждому листу Тф может быть приписана, вообще говоря, произвольная переменная из множества {x1,... ,xn} либо её отрицание. Под размером з(ф) формулы ф будем понимать число листьев n дерева Тф. В дальнейшем будем отождествлять каждую булеву формулу ф с деревом Тф. Обозначим через F множество всех булевых формул, а через - множество всех формул в F размера n. 1 /2n\ Лемма 1 [8]. |Fn| = 2ra_1(2n)raCra_i, где Cn =-I I - n-е число Каталана. n + 1 \ n J Для любой формулы ф определим множество Eq(ф) = {ф V ((x1 Л - x1) Л ф), ф - произвольная формула}. Очевидно, что ф выполнима тогда и только тогда, когда любая формула из Eq(ф) выполнима. Лемма 2. Для любой формулы ф имеет место |Eq^) nFra| > 1 |Fra| (16(n - 2))k для любого n > k + 2, где k - размер формулы ф. Доказательство. Пусть формула ф имеет размер k. Тогда для любой формулы ф V ((x1 Л - x1) Л ф) из множества Eq^) П Fn+2 формула ф должна иметь размер n - k. Кроме того, в этой формуле может участвовать любая из n переменных. Поэтому, аналогично тому, как это делалось в доказательстве леммы 1, можно подсчитать |Eq^) nFra+2| = 2n_fc_1(2n)n_fcCra_fc_1. Отсюда / 2(n - k - 1) |Eq^) nFra+2| 2n_fc_1(2n)n_fcC„_fc_1 1 C„_fc_1 1 n V n - k - 1 > |Fra+21 2ra_1(2n)raC„_1 (4n)k C„_1 (4n)k n - k ^2(n - 1) n - 1 1 (n - 1)! 2(n - k - 1)... (n - k) = 1 ((n - 1)... (n - k))2 > (4n)k (n - k - 1)! 2(n - 1) ...n = (4n)k 2(n - 1)... (2n - 2k - 1) > >_ (n - 1)... (n - k) ч2 > 1 1 _ 1 (4n)H 2(n - 1)... (2n - 2k - 1)7 (4n)k 22k (16n)fc' Таким образом, имеем ---.- > , откуда --- > -----. ■ |Fra+2| (16n)k |Fra| (16(n - 2))k Определим генерический аналог класса NP. Множество S С I принадлежит классу sgNP, если существует полиномиальное строго генерическое множество G С I, такое, что S П G G NP. Множество S G sgNP называется генерически NP-полным, если для любого A G SgNP имеет место A ^GenP S. Теорема 3. Проблема выполнимости булевых формул генерически NP-полна. Доказательство. Пусть A G sgNP. Тогда существует полиномиальное строго генерическое множество G, такое, что AП G G NP. Отсюда, по теореме Кука, следует, что существует классическая полиномиальная сводимость f множества A П G к проблеме выполнимости. Полиномиальный вероятностный алгоритм R, генерически сводящий проблему A к проблеме выполнимости, работает на входе (x, n) следующим образом: 1) проверяет, принадлежит ли x множеству G; 2) если x G G, выдаёт ?; 3) если x G G, то строит формулу ф = f (x), такую, что ф выполнима тогда и только тогда, когда x G A; 4) случайно и равновероятно генерирует формулу из множества Eq(0) П Fn. Как это делается за полиномиальное время, описано в [8]. Проверим свойства полиномиальной сводимости. Свойство 2 следует из того, что множество G строго генерическое. Свойства 1, а, б следуют из описания шага 4. Свойство 1, в очевидно выполняется: алгоритм вообще не выдаёт ответ !. Свойства 1, д, е также выполняются по построению формулы ф. Наконец, свойство 1, г следует из леммы 2. ■ Автор выражает благодарность рецензенту за полезные замечания и предложения по улучшению текста статьи.

Скачать электронную версию публикации

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 419 с.

Levin L. Average case complete problems // SIAM J. Computing. 1987. V. 15. P. 285-286.

Gurevich Y. Average case completeness // J. Computer System Sciences. 1991. V. 42. P. 346398.

Kapovichl., Miasnikov A, Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. No. 2. P. 665-694.

Gilman R., Miasnikov A. G., Myasnikov A. D., and Ushakov A. Report on generic case complexity // Herald of Omsk University. 2007. Special Issue. P. 103-110.

Impagliazzo R. and Wigderson A. P = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma // Proc. 29th STOC. El Paso: ACM, 1997. P. 220-229.

Cook S. A. The complexity of theorem proving procedures // Proc. 3d Annual ACM Symposium on Theory of Computing. N. Y., USA, 1971. P. 151-158.

Рыбалов А. О генерической сложности проблемы общезначимости булевых формул // Прикладная дискретная математика. 2016. №2(32). С. 119-126.