О предельных свойствах случайных КНФ

Задача выполнимости.

Задача выполнимости состоит в том, чтобы по произвольной булевой формуле определить, является ли она выполнимой, то есть существует ли набор значений переменных, на котором формула обращается в единицу. Теорема Кука гласит, что задача о выполнимости КНФ является NP-полной. fc-конъюнктивная нормальная форма (fc-КНФ) — это КНФ, в которой каждая элементарная дизъюнкция состоит из не более чем к литералов (букв). Задача^{-выполнимости} — это задача о выполнимости &—КНФ.

Известно, что для задачи 2-выполнимости существует алгоритм с полиномиальной сложностью (то есть задача 2-выполнимости принадлежит классу Р), в то время как при к > 2 задача^{-выполнимости} NP-полна. Эта задача является одной из наиболее исследуемых NP-полных задач. Целью диссертации является исследование некоторых числовых характеристик задачи о выполнимости случайных fc-КНФ.

История вопроса.

Один из первых математических результатов по алгоритмической сложности дискретных задач был получен С. В. Яблонским в 1959 г. (см. [14]) в ходе исследования алгоритмических трудностей синтеза минимальных схем. Суть результата состоит в том, что решение задачи построения бесконечной последовательности функций, имеющих сложную схемную реализацию, так называемыми &bdquo-правильными" алгоритмами непременно связано с перебором всех функций алгебры логики.

В 1962 г. в работе [8] Ю. И. Журавлев доказал, что для любого г существует такая функция, что никакой локальный алгоритм индекса г не может распознать свойство вхождения конъюнкции хотя бы в одну минимальную ДНФ.

В 1964 г. А. Н. Колмогоров ввел понятие сложности конечного объекта (например, слова в некотором алфавите). Сложность определялась как минимальная длина двоичной последовательности, содержащей информацию о задаваемом объекте, достаточную для его восстановления (см. [10]).

В 1971 году С. А. Кук в своей фундаментальной работе [11] ввел определение класса NP и доказал, что задача выполнимости является NP-полной (теорема Кука). Другими словами, он доказал, что любая задача из класса NP полиномиально сводится к задаче выполнимости. В частности, это означает, что если существует полиномиальный алгоритм для решения задачи выполнимости, то для каждой задачи из класса NP также существует полиномиальный алгоритм. Вопрос о равенстве классов сложности Р и NP остается одной из центральных открытых проблем в теории сложности.

В 1972 году Р. М. Карп существенно расширил список NP-полных задач. В частности, было доказано, что задача выполнимости полиномиально сводится к задаче 3-выполнимости (см. [9]). Заметим, что список известных NP-полных задач постоянно расширяется. В то же время, задача 2-выполнимости принадлежит классу Р.

Это обстоятельство привлекло внимание многих исследователей к задаче^{-выполнимости.} Изучение интенсивно ведется до сих пор. Для изучения &bdquo-типичных" fc-КНФ используется модель, когда формулы выбираются случайно и равновероятно из всех fc-КНФ длины т над п переменными. Задача оказалась интересной для физиков, так как она обладает свойствами, характерными для ряда физических моделей. Одним из таких свойств является существование порога выполнимости.

Порог выполнимости.

Будем строить случайные /г-КНФ путем случайного, равновероятного и независимого выбора m скобок (с повторением) из числа всех возможных скобок (элементарных дизъюнкций длины к над переменными xi, Х2, ¦ ¦., хп). Выбранную таким образом формулу будем обозначать Fk{n, m). Пусть к фиксировано, число переменных п стремится к бесконечности, а число скобок т равно гп, где г — некоторая константа. Пусть Sk (n, r) — вероятность того, что формула гп) выполнима.

Исследуем поведение предела вероятности выполнимости lim Sk{n, r).

П —>00.

Увеличение числа скобок в КНФ не может привести к увеличению вероятности выполнимости, а значит, предел вероятности выполнимости монотонно не возрастает nor (там, где этот предел существует). Определим верхний порог выполнимости, как точную верхнюю грань таких г, что вероятность выполнимости формулы все еще стремится к единице. Определим ииоюний порог выполнимости, rjjl, как точную нижнюю грань таких г, что вероятность выполнимости формулы стремится к нулю. Ясно, что Гк < г^. Существует предположение, что г к = г£ (предположение о пороге выполнимости, Chvatal, Reed, [23]). Такое число называется порогом выполнимости. Если предположение верно, то при увеличении г в определенный момент происходит скачок предела вероятности выполнимости от единицы к нулю.

Существование порога в виде некоторой константы не доказано, но известно следующее утверждение:

Утверждение 1. (Friedgut, [30]) Для любого к > 2 сугцествует такал последовательность г kin), что для любого е > О lim Sk (n, (1 — e) rk (n)) = 1,.

П—>00 lim Sk (n, (1 + e) rfc (n)) = 0. n—>oo.

Здесь роль порога выполняет последовательность гк (п). Если у нее есть предел, то порог выполнимости существует и равен этому пределу.

Следствие 1. Зафиксируем к > 2. Если Fk (n, r*n) выполнима с вероятностью Рп > С > 0, то при г < г* вероятность выполнимости F) t (n, rn) стремится к единице.

Мы говорим, что последовательность событий Ап происходит с высокой вероятностью, если lim Р (Л") = 1. Для упрощения записи будем.

П-> 00 говорить, что Гк > г*, если Fk (n, rn) выполнима с высокой вероятностью при г < г*. Будем говорить, что гк < г*, если Fk (n, rn) с высокой вероятностью не выполнима при г > г*. Следствие 1 означает, что г к > г если вероятность выполнимости Fk (n, rn) ограничена снизу положительной константой.

Цели изучения случайных КНФ.

Изучение предельных свойств случайных КНФ можно рассматривать как продолжение изучения случайных функций. Модели похожи как по геометрическим свойствам (например, наличие кластеризации), так и по успешно применяющимся методам (например, метод вторых моментов), см. [12], [7].

Многие исследователи выражали скептицизм по поводу попыток связать изучение порога выполнимости с вопросами вычислительной сложности. В то же время, изучение числовых характеристик такой модели может позволить сделать выводы о более общем случае. В качестве примера можно привести результаты последних лет, согласно которым возрастание сложности вычислений вблизи порога связано с эффектом кластеризации, когда множество выполняющих наборов функции разбивается на небольшие подмножества, причем расстояния между подмножествами относительно велики.

Изучение случайных КНФ имеет значение для разработки алгоритмов, решающих задачу выполнимости, а также для генерирования формул, на которых эти алгоритмы тестируются.

В 85-м году Y. Fu и P. Anderson в работе [32] впервые предположили существование значительной связи между NP-полными задачами и моделями статистической физики, такими как модель Изинга. Одно из общих свойств — существование порога (фазового перехода) и резкое возрастание сложности вычислений вблизи порога. Прослеживаются аналогии между задачей выполнимости случайной fc-КНФ и моделями спинового стекла (материалов с неупорядоченной магнитной структурой, см. [42], [19]).

В связи с этим, исследованием модели случайной &—КНФ стали заниматься физики (М. Mezard, R. Monasson, G. Parisi, R. Zecchina и другие). Методы, которыми они пользовались для анализа моделей статистической физики, удалось успешно применить и к случайным fc-КНФ. Предложенный ими алгоритм для поиска выполняющих наборов случайной.

— КНФ (Survey propagation) по эффективности превосходит все прочие алгоритмы. Survey propagation за несколько минут находит выполняющий набор случайной 3-КНФ при п = 106, г = 4,25 (предполагаемое значение порога — 4,27). Сложность вычислений при этом растет как O (nlnn). Все остальные известные алгоритмы не способны справиться с подобной задачей за разумное время даже при п — 104 (см. [45]).

Порог fc-выполнимости.

В 83-м году J. Franco и М. Paull в работе [29] с помощью неравенства Маркова доказали, что г&- < 2fcln2. Зафиксируем значения переменных жх,., хп. Вероятность того, что случайная fc-буквенная скобка обращается в единицу на этих значениях, равна 1 — 2~к. Следовательно, математическое ожидание числа выполняющих наборов для Fk (n, rn) равно (2(1 — 2~к)г)п = о (1) при г > 2* In 2, а значит, вероятность того, что у Fk (n, rn) есть выполняющие наборы, также равна о (1) при г > 2к In 2. В 90-м году М. Chao и J. Franco в работе [21] дополнили этот результат, доказав, что алгоритм UNIT CLAUSE находит выполняющий набор для формулы с положительной вероятностью при г < 2к/к. Этот алгоритм был впервые описан в работе [20]. На каждом шаге алгоритма одной из переменных х,., жп присваивается 0 или 1 (при этом все скобки, в которые входит эта переменная, становятся короче или обращаются в единицу). Переменным присваиваются значения по следующим правилам. Если в формуле есть однобуквенная скобка, обращаем ее в единицу. Иначе выбираем любую переменную и присваиваем ей 0 или 1 случайно и равновероятно. Алгоритм не срабатывает, если на очередном шаге получается скобка длины 0. Если же этого не происходит, то алгоритм находит выполняющий набор для исходной формулы.

Примерно в это же время на основе экспериментальных результатов P. Cheeseman, В. Kanefsky и W. Taylor (работа [22]) и D. Mitchell, В. Selman и Н. Levesque (работа [43]) возникло предположение, что случайная &—КНФ ведет себя подобно физической системе в том смысле, что она проходит через фазовый переход. Впервые предположение о пороге выполнимости, видимо, появилось в работе [23], там же было доказано, что r2 = г2 = 1 и Tk > (3/8)2к/к (нижняя оценка была получена с помощью анализа алгоритма UNIT CLAUSE). В 96-м году A. Frieze и S. Suen в работе [31] улучшили эту оценку до > ск2к/к, где lim = 1,817. к-^оо.

Улучшение снова было получено с помощью анализа алгоритмов: к алгоритму из работы [23] была добавлена возможность делать несколько шагов назад в случае, когда на очередном шаге возникает пустая скобка.

В 1997;м году физики-теоретики R. Monasson и R. Zecchina в работе [44] с помощью метода «replica trick» предсказали, чтог&- ~ 2fcln2.

Были сделаны дальнейшие попытки улучшить нижнюю оценку c2k/k с помощью анализа алгоритмов. К сожалению, этот подход сводится к выбору между простыми алгоритмами, не дающими улучшения оценки, и более сложными алгоритмами, для которых не удается оценить вероятность успешной работы. Алгоритмические методы не только дают нижнюю оценку вероятности выполнимости формулы, но и находят выполняющий набор. Один из способов избежать такой избыточности — применение метода вторых моментов. Как правило, при попытке использования метода вторых моментов для задачи выполнимости оказывается, что дисперсия случайной величины растет гораздо быстрее, чем квадрат математического ожидания. Но в 2002;м году D. Achlioptas и С. Moore в работе [15] успешно применили метод вторых моментов для улучшения нижней оценки Они рассмотрели случайную величину, равную числу таких выполняющих наборов случайной fc-КНФ, что в каждой скобке хотя бы одна буква обращается в ноль.

В 2004;м году они развили этот подход в работе [16] и доказали следующее широко известное утверждение.

Утверждение 2. Существует такая последовательность —У 0, что для всех к > 3 выполняется неравенство гк>2кп2-(к+1)^-1−5к.

Таким образом, удалось доказать, что rk ~ 2fcln2 (при к —У об). Кроме того, в работе [16] были получены конкретные нижние оценки для всех к > 3, тем самым были улучшены предыдущие нижние оценки для всех к кроме 3 (для к = 3 алгоритмические методы дают существенно лучшие результаты).

Порог 2-выполнимости.

Порог 2-выполнимости был найден в 92-м году. Независимо V. Chvatal и В. Reed в работе [23] и A. Goerdt в работе [34] доказали, что г2 = 1. Основной прием, использующийся при исследовании 2-выполнимости, — представление 2-КНФ в виде ориентированного графа. КНФ обращается в единицу на наборе значений тогда и только тогда, когда каждая ее скобка обращается в единицу. Заметим, что если в 2-КНФ F присутствует скобка {ха V?/r), то выполняющий набор для F обладает следующим свойством. Из х = а следует у = тпи. зу = т следует х = о. Так что скобка (ха V ут) соответствует условиям х = а =Фу = т, у = т х = ст. Построим орграф Gp по 2-КНФ следующим образом. Его множество вершин Vp равно {х,., хП1 aifi,., аГп}, множество дуг Ер равно {х&- —> ут в F есть скобка (ха V ут)}. Поскольку (ха V ут) и (ут V ха) это одна и та же скобка, в графе Dp есть дуга ха —У ут тогда и только тогда, когда в нем есть дуга ут —> ха.

Ориентированный маршрут в графе — это такая последовательность вершин г? о, V,., vi, что для всех i = 1,., 1 в графе есть дуга —>• V{. Такой маршрут называется маршрутом из vq в Будем писать и v если в Gp есть ориентированный маршрут из и в v. Для простоты будем считать, что v i—> v для всех v. Наконец, будем говорить, что Gp содержит противоречащий цикл, если Xi н-у х^ и щ Xi для некоторой переменной xi G {жь ., хп}.

Следующая лемма позволяет свести задачу о выполнимости 2-КНФ F к задаче проверки одного из свойств орграфа Gp.

Лемма 1. (Goerdt, [33]) 2-КНФ F выполнима тогда и только тогда, когда орграф Gp не содержит противоречащих циклов.

При к > 2 подобный подход применить не удалось.

Порог 3-выполнимости.

Улучшение нижней оценки порога 3-выполнимости как правило производилось с помощью анализа простых алгоритмов. В каждом таком алгоритме на очередном шаге одной из переменных присваивается значение.

О или 1. Ниже приведены правила, по которым работают эти алгоритмы, когда в формуле нет однобуквенных скобок и &bdquo-чистых" переменных (входящих в формулу только без отрицания или только с отрицанием). В порядке увеличения эффективности:

UNIT-CLAUSE ([23]): выбрать случайную переменную и присвоить ей случайное значение.

3-CLAUSE MAJORITY ([20]): выбрать случайную переменную и присвоить ей значение так, чтобы как можно больше трехбуквенных скобок обратилось в единицу.

SHORT-CLAUSE ([31]): выбрать случайную кратчайшую скобку с, выбрать случайную букву в с и обратить ее в единицу.

HAPPIEST LITERAL ([36]): обратить в единицу букву, входящую в наибольшее число скобок.

В первом случае выбор переменной происходит независимо от формулы, в последнем — для выбора переменной требуется вся информация о формуле. Соответственно, отношение числа скобок к числу переменных, при котором алгоритм находит выполняющий набор с положительной вероятностью, растет от 8/3 для [23] до 3,42 для [36].

Предложенный физиками алгоритм Survey propagation, несмотря на свою эффективность, не подходит для улучшения оценок порога выполнимости, так как слишком сложен для строгого анализа. Тем не менее, он помог пролить свет на причины, по которым терпят неудачу названные выше простые алгоритмы, и в конечном итоге — на структуру множества решений типичной задачи ^-выполнимости.

Для получения простейшей верхней оценки порога 3-выполнимости можно использовать неравенство Маркова. Как было показано выше, математическое ожидание числа выполняющих наборов для Fk (n, rn) равно (2(1 — 2~ку)п. При к = 3 это выражение равно (2(7/8)г)" = о (1) при г > log7/s (l/2). Следовательно, гз < log7/8(l/2) «5,19.

В 95-м году A. El Maftouhi и F. de la Vega в работе [40] улучшили эту оценку до гз < 5,08. В том же году A. Kamath и другие в работе [46] получили оценку гз < 4,758 с помощью вычислений и аналитически доказали оценку гз < 4,87. В 96-м году L. Kirousis, Е. Kranakis и.

D. Krizanc в работе [38] рассмотрели случайную величину, равную числу таких выполняющих наборов формулы, что при замене любого нуля на единицу набор перестает быть выполняющим. Применив неравенство Маркова к этой случайной величине, они получили оценку гз < 4,667. В 97-м году О. Dubois и Y. Boufkhad в работе [26] использовали ту же случайную величину, но провели более точные вычисления и получили оценку гз < 4,642. Обобщив этот подход, в 98-м году L. Kirousis и другие в работе [18] улучшили оценку до гз < 4,602. В 2000;м году S. Janson, Y. Stamatiou и М. Vamvakari в работе [35] представили 3-КНФ в виде физической спиновой системы и использовали методы статистической физики для оценки асимптотики ее энергии, в результате удалось доказать, что гз < 4,596. В своей докторской диссертации ([48]) М. Zito улучшил оценку до гз < 4,58. В 2001;м году A. Kaporis и другие в работе [47] получили оценку гз < 4,571, использовав верхнюю оценку для обобщенных биномиальных коэффициентов из работы [39]. Наконец, О. Dubois, Y. Boufkhad и J. Mandler исследовали множество формул, в которые каждая переменная входит &bdquo-типичное" число раз (с учетом знака), и доказали, что гз < 4,506 (см. [27], [28]).

Кластеризация.

Итак, метод вторых моментов позволил получить нижнюю оценку для порога квыполнимости г к = 2fc In 2 — О (к), в то время как лучшая алгоритмическая нижняя оценка имеет видс2к/к. В 2006;м году D. Achlioptas и F. Ricci-Tersenghi в работе [17] доказали следующее утверждение, объясняющее, почему не происходит дальнейшее улучшение нижних оценок для порога^{-выполнимости} с помощью алгоритмических методов.

Утверждение 3. При любом к > 8 существуют г < Тк и константы oik < Pk < ½ и Ek > 0, такие, что с высокой вероятностью множество выполняющих наборов случайной формулы Fk (n, rn) состоит из 2£кП непустых множеств связанных кластеров, таких, что.

1. Диаметр каждого множества кластеров не превосходит оскП,.

2. Расстояние мео/сду любыми двумя множествами кластеров не меньше fan.

Краткое содержание диссертации.

Во введении обоснована актуальность темы исследования, рассмотрена история вопроса, описана структура диссертации и перечислены основные результаты.

В первой главе предложена модификация метода получения нижних оценок для порога fc-выполнимости при к > 3, описанного в работе [16]. В параграфе 1.4 найдена функция дг (а,/3), зависящая от параметров г, го (1),., w (k), такая, что верна следующая теорема.

Теорема 1. Пусть для фиксированного г существуют w{i), г = 1, к и кусочно-постоянная функция Ь (а) > 1, такие, что для всех, а ^ ½ выполняется неравенство gr (l/2,l) > gr (a, b (a)). Пусть кроме того g" (a, 1) < 0 при, а = ½. Тогда г — ниэ1сняя оценка порога к-выполнимости.

В параграфе 1.5 с помощью этой теоремы улучшены нижние оценки порога /с-выполнимости при к = 4, 5, 6, 7.

Теорема 2. г4 > 8,09, г5 > 18,91, г6 > 40,81, г7 > 84,87.

Во второй главе рассматривается вопрос присутствия во множестве выполняющих наборов случайной fc-КНФ граней различных размерностей.

В параграфе 2.1 оценено число фиктивных переменных в случайной fc-КНФ.

Теорема 3. Пусть с — константа, с < e~kr. Тогда с высокой вероятностью (Р —> 1 при п —> оо) не менее сп из переменных х,., хп не войдут в формулу Fi-(n, rn).

Отсюда следует, что при г < г^, с < e~kr множество выполняющих наборов случайной формулы (обозначаемоеА^(П)ГП)) с высокой вероятностью может быть разбито на грани одного направления размерности сп.

Кроме того, в параграфе 2.1 сделано предположение о существовании порога присутствия граней:

Предположение. (О пороге присутствия граней) Для любого к > 2 и для любого s, 0 < s < 1, существует такое гк, 3> что если т < Vk, s) mo с высокой вероятностью в NFk (n, rn) найдется грань размерности ns, если г > rk, s> то с высокой вероятностью в Л^(П)Г7г) отсутствуют грани размерности ns.

В параграфе 2.2 доказано существование порога в форме последовательности для присутствия граней.

Теорема 4. Для всех к > 2 и s G (0,1) существует такая последовательность rf~jS (n), что для любого е > О если г = (1 — ?)rk, s (ri), то с высокой вероятностью в Ny^^ найдется грань размерности ns, если г = (1 + ?)rk, s{n), тпо с высокой вероятностью в NFk^n>rn^ отсутствуют грани размерности ns.

Отсюда следует, что если при s? (0,1), г > 0, к > 3 вероятность присутствия вА^(П)Гтг) грани размерности ns ограничена снизу положительной константой, не зависящей от п, то > г.

В параграфе 2.4 найден метод получения нижних оценок порога присутствия граней размерности ns в Np^m) ПРИ к > 3. Точнее, найдена функция gr (cx,/3), зависящая от параметров г, w (l),., w (k), такая, что верна следующая теорема.

В параграфе 2.5 продемонстрирована эффективность метода при к =.

Теорема д (а,/3) при всех (а, /3) ф.

Основные результаты диссертации.

1. Улучшен метод получения нижних оценок порога^{-выполнимости} при к > 3.

2. Улучшены нижние оценки порога^{-выполнимости} для к = 4,5,6,7.

3. Доказано существование порога в форме последовательности для присутствия граней.

4. Найден метод получения нижних оценок порога присутствия граней размерности ns в Л^(П)ГП) при к > 3.

1. Воробьев, Ф. Ю. О нижней оценке порога 4-выполнимости / Ф. Ю. Воробьев //V1.Международная конференция &bdquo-Дискретные модели в теории управляющих систем". — М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2004.— С. 24.

2. Воробьев, Ф. Ю. О нижней оценке порога 4-выполнимости / Ф. Ю. Воробьев // Тезисы докладов XIV Международной конференции &bdquo-Проблемы теоретической кибернетики" .— М.: Изд-во механико-математического факультета МГУ, 2005. — С. 31.

3. Воробьев, Ф. Ю. О нижней оценке порога 4-выполнимости / Ф. Ю. Воробьев // Дискретная математика.— 2007.— Т. 19, № 2. С. 101−108.

4. Воробьев, Ф. Ю. О структуре множества выполняющих наборов случайной &—кнф / Ф. Ю. Воробьев // Прикладная математика и информатика. 2007. — Т. 26. — С. 61−95.

5. Воробьев, Ф. Ю. О числе выполняющих наборов случайной &—кнф / Ф. Ю. Воробьев // Материалы IX Международного семинара &bdquo-Дискретная математика и ее приложения". — 2007. — С. 210−212.

6. Воробьев, Ф. Ю. Улучшение нижних оценок порога^{-выполнимости} для небольших к / Ф. Ю. Воробьев // Материалы VI молодежной научной школы по дискретной математике и ее приложениям. — № 1. 2007. С. 21−26.

7. Глаголев, В. В. Некоторые оценки дизъюнктивных нормальныхформ / В. В. Глаголев // Проблемы кибернетики. — 1967. — Т. 19. — С. 75−94.

8. Журавлев, Ю. И. Теоретико-множественные методы в алгебре логики / Ю. И. Журавлев // Проблемы кибернетики. — 1962. — Т. 8. —C. 5−44.

9. Карп, Р. М. Сводимость комбинаторных проблем / Р. М. Карп // Кибернетический сборник (Нов. серия). — 1975. — Т. 12. — С. 16−38.

10. Колмогоров, А. Н. Теория информации и теория алгоритмов / А. Н. Колмогоров. — Наука, 1987.

11. Кук, С. А. Сложность процедур вывода теорем / С. А. Кук // Кибернетический сборник (Нов. серия). — 1975.—- Т. 12.— С. 5−10.

12. Сапоженко, А. А. Геометрическое строение почти всех функций алгебры логики / А. А. Сапоженко // Проблемы кибернетики. — 1975. Т. 30. С. 227−261.

13. Сапооюеико, А. А. Некоторые вопросы сложности алгоритмов / А. А. Сапоженко. — Издательство факультета ВМиК МГУ, 2001.

14. Яблонский, С. В. О невозможности элиминации перебора всех функций из р2 при решении некоторых задач теории схем / С. В. Яблонский // ДАН СССР. 1959. — Т. 124, № 1. — С. 44−47.

15. Achlioptas, D. The asymptotic order of the random k-sat threshold /D. Achlioptas, C. Moore // Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science / Ed. by C. Moore. — 2002. — Pp. 779 788.

16. Achlioptas, D. The threshold for random k-sat is 2&ln2 — o (k) / D. Achlioptas, Y. Peres // J. Amer. Math. Soc. 2004. Vol. 17.-Pp. 947−973.

17. Achlioptas, D. On the solution-space geometry of random constraint satisfaction problems / D. Achlioptas, F. Ricci-Tersenghi //In proc. 38thannual ACM symposium on theory of computing. — 2006.— Pp. 130 139.

18. Biroli, G. Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem / G. Biroli, S. Cocco, R. Monasson // Physica A. — 2002. — Vol. 306. — Pp. 381−394.

19. Chao, M.-T. Probabilistic analysis of two heuristics for the 3-satisfiability problem / M.-T. Chao, J. Franco // SIAM J. Comput. — 1986. Vol. 15, no. 4. — Pp. 1106−1118.

20. Chao, M.-T. Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the^{-satisfiability} problem / M.-T. Chao, J. Franco // Inform. Sci.- 1990. Vol. 51, no. 3. Pp. 289−314.

21. Cheeseman, P. Where the really hard problems are / P. Cheeseman, B. Kanefsky, W. Taylor //In Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI-91). 1991. — Vol. 1. — Pp. 331−337.

22. Chvatal, V. Mick gets some (the odds are on his side) / V. Chvatal, B. Reed //In Proc. 33th Annual Symposium on Foundations of Computer Science. 1992. — Pp. 620−627.

23. Dubois, О. A general upper bound for the satisfiability threshold of random r-sat / O. Dubois, Y. Boufkhad // X Algorithms. — 1997. — Vol. 24. — Pp. 395−420.

24. Dubois, O. Typical random 3-sat formulae and the satisfiability threshold / O. Dubois, Y. Boufkhad, J. Mandler // Electronic Colloquium on Computational Complexity (ECCC). — 2003. — Vol. 10, no. 7.

25. Franco, J. Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem / J. Franco, M. Paull // Discrete Appl. Math. 1983. — Vol. 5, no. 1. — Pp. 77−87.

26. Friedgut, E. Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-sat problem / E. Friedgut // J. Amer. Math. Soc. 1999. — Vol. 12. — Pp. 1017−1054.

27. Frieze, A. M. Analysis of two simple heuristics on a random instance of k-sat / A. M. Frieze, S. Suen // J. Algorithms. — 1996. — Vol. 20, no. 2. Pp. 312−355.

28. Goerdt, A. A threshold for unsatisfiability / A. Goerdt // Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science. — 1992. Pp. 264−274.

29. Goerdt, A. A threshold for unsatisfiability / A. Goerdt // J. Comput. Syst. Sci.- 1996. Vol. 53, no. 3. — Pp. 469−486.

30. Janson, S. Bounding the unsatisfiability threshold of random 3-sat / S. Janson, Y. C. Stamatiou, M. Vamvakari // Random Struct. Algorithms.— 2000. Vol. 17, no. 2. Pp. 103−116.

31. Kaporis, A. C. The probabilistic analysis of a greedy satisfiability algorithm / A. C. Kaporis, L. M. Kirousis, E. G. Lalas // ESA '02: Proceedings of the 10th Annual European Symposium on Algorithms. — London, UK: Springer-Verlag, 2002. Pp. 574−585.

32. Karp, R. M. Reducibility among combinatorial problems / R. M. Karp // Complexity of Computer Computations / Ed. by R. E. Miller, J. W. Thatcher. Plenum Press, 1972. Pp. 85−103.

33. Kirousis, L. M. Upper bounds and asymptotics for the q-binomial coefficients / L. M. Kirousis, Y. C. Stamatiou, M. Vamvakari // Stud. Appl. Math. 2001. — Vol. 107. — Pp. 43−62.

34. Maftouhi, A. E. On random 3-sat / A. E. Maftouhi, W. F. de la Vega // Combinatorics, Probability & Computing. — 1995. —Vol. 4.— Pp. 189 195.

35. Mezard, M. Pairs of sat assignment in random boolean formulae / M. Mezard, T. Mora, R. Zecchina // CoRR.- 2005. Vol. abs/cond-mat/506 053.

36. Mezard, M. Spin Glass Theory and Beyond (World Scientific Lecture Notes in Physics, Vol 9) / M. Mezard, G. Parisi, M. Virasoro. — World Scientific Publishing Company, 1987.

37. Monasson, R. Statistical mechanics of the random^{-satisfiability} model / R. Monasson, R. Zecchina // Phys. Rev. E (3).— 1997. Vol. 56, no. 2. Pp. 1357−1370.

38. Robinson, S. Math/physics collaboration sheds new light on computational hardness / S. Robinson // SIAM News. 2005. — Vol. 38, no. 4.

39. Tail bounds for occupancy and the satisfiability threshold conjecture / A. P. Kamath, R. Motwani, K. Palem, P. Spirakis // Random Structures and Algorithms. 1995. — Vol. 7. — Pp. 59−80.

40. The unsatisfiability threshold revisited / A. C. Kaporis, L. M. Kirousis, Y. C. Stamatiou et al. // LICS 2001 Workshop on Theory and Applications of Satisfiability Testing (SAT-01). 2001.

41. Zito, M. Randomised techniques in combinatorial algorithmics: Tech. rep. / M. Zito. Coventry, UK, UK: University of Warwick, 1999.— November.