Backdoors in combinatorial problems and their probabilistic generalizations.pdf Понятие «лазейка» в применении к произвольной задаче удовлетворения ограничений (Constraint Satisfaction Problem, CSP) впервые дано в работе [1]. Нас в дальнейшем будут, в первую очередь, интересовать «сильные лазейки» (Strong Backdoor Sets), также введённые в [1]. Рассмотрим проблему булевой выполнимости (SAT) как один из простейших и наиболее наглядных примеров CSP. В произвольном экземпляре SAT фигурирует булева формула C (обычно в конъюнктивной нормальной форме, КНФ). Множество встречающихся в C переменных со значениями в {0, 1} обозначим через X . Элементарными ограничениями являются дизъюнкты, входящие в C. Для произвольного B С X обозначим через {0, 1}|B| множество всех наборов значений переменных из B. Подстановка значения а 6 {0, 1} произвольной переменной x 6 X в формулу C определяется стандартным образом [2]. Обозначим через C [в/B] КНФ, которая получается в результате подстановки в C набора в значений переменных из B. Пусть O - некоторый полиномиальный алгоритм. Определение 1 [1]. Сильной лазейкой (Strong Backdoor Set, SBS) для КНФ C относительно алгоритма O называется такое множество B С X, что для любого в 6 {0,1}|B| задача выполнимости КНФ C [в/B] разрешима алгоритмом O. Таким образом, если B - сильная лазейка для КНФ C, то задача выполнимости C решается за время poly(|C|) 2|B|, где poly(-) -некоторый полином; |С| -длина двоичного описания C. Можно привести массу примеров, когда C содержит сильную лазейку, число переменных в которой может не превосходить нескольких процентов (или даже долей процента) от общего числа переменных в X. Таковы, например, КНФ, кодирующие задачи криптоанализа. В этих случаях множество переменных, кодирующих вход рассматриваемой криптографической функции, образует SBS относительно простейшего правила распространения булевых ограничений - правила единичного дизъюнкта (Unit Propagation rule, UP). Например, КНФ, кодирующая задачу поиска прообраза криптографической функции SHA-256, то есть задачу обращения функции fSHA-256 : {0, 1}512 - {0, 1}256, имеет SBS относительно правила UP, которое состоит из 512 переменных, при том что общее число переменных в данной КНФ равно 49 098. Легко понять, что сильная лазейка размерности существенно меньше 512, если бы она существовала, давала бы нетривиальную атаку на данную функцию. Очевидный интерес представляют сильные лазейки наименьшей мощности, поскольку они дают лучшие верхние границы в рассматриваемом классе таких границ. Определение 2. Для произвольной КНФ C и полиномиального алгоритма O сильную лазейку относительно O наименьшей мощности будем называть минимальной. Теорема 1 [1]. Если КНФ C содержит сильную лазейку размера |В| С |Х|/2, то существует алгоритм, который решает SAT для C за время poly(|C|) (1) Следствие 1 [1]. Для формул с сильной лазейкой размера не более n/4,404 проблема SAT может быть решена детерминированным образом за время O (cn), где c < 2. Алгоритм из [1] (далее - «алгоритм А»), который подразумевается в формулировке теоремы 1, очень прост. Сначала проверяются на свойство быть сильной лазейкой все множества, состоящие из одной переменной - их n = |X |, затем - все множества из двух переменных - их , и так далее. Очевидно, что первая сильная лазейка, найденная алгоритмом A, минимальная. С другой стороны, в худшем случае алгоритм A пройдёт все подмножества множества X и переберёт все 2n наборов значений переменных из X. Таким образом, в худшем случае сложность данного алгоритма есть следующая величина с точностью до некоторого полиномиального от |C| сомножителя: Е i=1 (;)- s n 2i - 1 = 3n - 1. (2) Следствие 1 означает, что если существует сильная лазейка мощности С |Х | /2, то даже алгоритм A может быть асимптотически (на соответствующем семействе формул) лучше полного перебора. Оценку (1) можно переписать в более наглядной форме. Это делается за счёт анализа биномиальных коэффициентов и использования формулы Стирлинга. Заметим, что в случае существования лазейки мощности K имеет место Kn TA С p(|C|) Е 2j, где p(-) - некоторый полином, что для K С n/q и q > 2 с учётом i=1 i свойств биномиальных коэффициентов даёт следующую оценку: Ta С p(|C|)2*(£)• (3) Преобразуя (3) с использованием формулы Стирлинга, имеем Следствие 2. Если КНФ C содержит сильную лазейку мощности K = |_n/qj, q 2, то существует алгоритм, решающий SAT для C за время Ta, где Ta С p(|C|)2 n(1/q+log q-(q-1)log(q-1)/q) (4) К сожалению, использование (4) не даёт существенного улучшения оценки из [1]. Конкретно, (4) даёт следующий результат (аналог следствия 4.2 из [1]), который полу-1 q - 1 чен за счёт решения пакетом WolframAlpha уравнения -+ log q--log(q - 1) = 1: qq Следствие 3. Для формул с сильной лазейкой размера не более n/4,40349 проблема SAT может быть решена детерминированным образом за время O (cn), где c < 2. Соотношение (2) означает, что алгоритм A крайне неэффективен в применении к поиску минимальной сильной лазейки и вряд ли может использоваться для решения практических задач. При детальном рассмотрении становится понятно, что основной фактор неэффективности A - это необходимость проверять свойство произвольного B С X быть сильной лазейкой: для этого требуется проверить разрешимость C[в/В] алгоритмом O для каждого в € {0,1}|в| (делая, таким образом, каждый раз 2|в| проверок). В работе [3] предложено вероятностное обобщение понятия сильной лазейки. Соответствующее определение выглядит следующим образом. Определение 3. Пусть C - произвольная КНФ, X - множество переменных в C и O - некоторый полиномиальный алгоритм. Произвольное множество B С X назовём р-лазейкой, р € [0,1], относительно алгоритма O, если среди всех задач вида C[в/В], в € {0, 1}|B| , доля задач, решаемых алгоритмом O, составляет не менее р. Очевидно, что р-лазейка с р = 1 -это сильная лазейка. Если р < 1, то с практической точки зрения важно, чтобы р было как можно ближе к 1. Действительно, если В - такая р-лазейка, то мы можем алгоритмом O решить р • 2|B| задач вида C[в/В], а к оставшимся (1 - р) 2|B| задачам применить полный алгоритм решения SAT. Если считать р, проверяя, решается ли алгоритмом O каждая задача вида C[в/В], то соответствующая процедура, как и в случае сильных лазеек, неэффективна. Однако, как показано в [3], можно эффективно оценить р, используя простой вероятностный тест. Для произвольных C над X, В С X и полиномиального алгоритма O зададим на {0, 1}|B| равномерное распределение и определим случайную величину f в : {0, 1}|B| - {0, 1}, которая принимает на в € {0,1}|в| значение 1, если C[в/В] решается алгоритмом O и значение 0 в противном случае. Очевидно, что если В - р-лазейка, то вероятность успеха в наблюдении величины f в составляет не менее р и, таким образом, E [^в] Y р. Последнее означает, что можно оценивать параметр р произвольного В С X, оценивая величину E [^в]• Поскольку вв - случайная величина Бернулли, то для оценки E [^в] можно использовать следующее неравенство (являющееся вариантом известной границы Чернова): г 1 N P N Е fj - E Кв] 1 - 5. Теперь мы можем определить вероятностный аналог сильной лазейки. Определение 4 [3]. Назовём B сильной (е, 5)-лазейкой, если B проходит описанный тест Монте-Карло. Например: если B проходит тест при е = 5 = 0,01, то с вероятностью 99% можно заключить, что B - это р-лазейка с р 0,98 (то есть р очень близко к 1). Нетрудно заметить, что сложность описанного алгоритма оценивания E [£в] при фиксированных е, 5 е (0,1) ограничена сверху величиной p(|C|)16ln (2/5)/е2 и, следовательно, данный алгоритм эффективный. Таким образом, в противовес алгоритму A, перебирающему множества B последовательно возрастающей мощности, мы можем искать сильные (е, 5)-лазейки, минимизируя некоторую целевую функцию при помощи метаэвристических алгоритмов на множестве всех подмножеств X. Более конкретно, с произвольным B С X в [3] связывается значение следующей функции: ФС,А^ (В) = рв • 2|B| + GC,A,N (B). (6) В (6) часть Gc,a,n (B) -это штрафная функция: её значение должно резко возрастать при уменьшении величины рв. В [3] использована штрафная функция вида „ _((1 - рв)2ш|Х|, если рв > 0; GC,A,N = I то, если рв = 0, где ш е (0,1) -параметр, подбираемый эмпирически для каждой конкретной КНФ C. Как сказано ранее, для решения задач вида C[в/B], не разрешимых полиномиальным алгоритмом O, можно использовать полный SAT-решатель. Для решения SAT в отношении трудной C можно использовать также несколько найденных сильных (е, 5)-лазеек. Пусть B1,... , Bs - такие лазейки. Для каждого Br, r е {1,..., s}, построим множество Дг, состоящее из всех таких в е {0,1}|вг|, что C[в/Вг] не разрешима алгоритмом O. Заметим, что мощность каждого Дг, r е {1,... , s}, может составлять доли процента от 2|вг|. Рассмотрим декартово произведение Д = Д1 х ... х Дг. Заметим, s что каждый вектор из Д состоит из |Br| бит и, следовательно, его подстановка в C r=1 может существенно упростить задачу. При этом мощность Д равна где рГ -доля таких в е {0,1}|вг|, что C[в/B] решается алгоритмом O. При близких к 1 величинах рГ, r е {1,... , s}, величина (7) может быть разумной, и соответствующие SAT-задачи оказываются простыми для современных SAT-решателей. (Й (1 - рг)} nt |вг | 2r=1 , (7) В [3] проведены вычислительные эксперименты по поиску сильных (е, 5)-лазеек, которые подтвердили, что во многих комбинаторных задачах часто встречаются такие лазейки, имеющие малую мощность. Иногда их использование позволяет ускорить решение исходной SAT-проблемы в десятки и сотни раз. Поиск сильных (е, 5)-лазеек может рассматриваться как задача минимизации функции вида (6), для чего можно применять любой алгоритм псевдобулевой оптимизации. В [3] для минимизации функций вида (6) использован генетический алгоритм. Эксперименты проводились на вычислительном кластере с помощью программной системы EvoGuess [5]. В роли алгоритма O выступало простейшее правило единичного дизъюнкта [6]. Следует отметить, что концепция сильных (е, 5)-лазеек может быть естественным образом перенесена на любую задачу удовлетворения ограничений. Например, пусть I - произвольная задача целочисленного линейного программирования (ILP, Integer Linear Programming) и X - множество фигурирующих в постановке I переменных со значениями в {0, 1} (таким образом, речь идет о 0-1-ILP). Напомним, что в стандартной подстановке для решения I требуется минимизировать (или максимизировать) некоторую функцию при ограничениях, заданных системой целочисленных неравенств следующего вида: Ax > b, (8) где A - целочисленная матрица размера m х n; b - целочисленный вектор длины m; x = (xi,... , xn) -вектор переменных, принимающих значения в {0,1}. По аналогии мы можем ввести множество булевых переменных X = {xi, . . . , xn}, рассмотреть произвольное B, B С X, а в качестве полиномиального алгоритма взять алгоритм преобразования системы неравенств (8) после подстановки в неё произвольного в G {0,1}|B|. Далее можем искать р-лазейки и, в частности, сильные (е, 5)-лазейки, используя шаги, аналогичные описанным выше. Первые вычислительные эксперименты в этом направлении (с использованием ILP-решателей Gurobi и SCIP) показали работоспособность концепции вероятностных лазеек: для некоторых трудных 0-1-ILP-задач найденные лазейки дают ускорение в десятки раз.

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