О предельных свойствах случайных КНФ тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет имени М В. Ломоносова

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

Специальность 01.01 09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

Воробьев Федор Юрьевич

Москва - 2008

0031674320S

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М В, Ломоносова.

Научный руководитель доктор физико-математических наук,

профессор

Александр Антонович Сапоженко

Официальные оппоненты: доктор физико-математических наук,

руководитель отдела ИСП РАН Николай Николаевич Кузюрин,

кандидат физико-математических наук, с.н с ВЦ РАН

Михаил Николаевич Вялый.

Ведущая организация

Институт системного анализа РАН

Защита диссертации состоится 16 мая 2008 г. в И . 00 на заседании диссертационного совета Д 501 001.44 в Московском государственном университете им. M В Ломоносова по адресу 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-ой учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК

С текстом автореферата можно ознакомиться на официальном сайте факультета ВМиК Московского государственного университета имени М В Ломоносова Шр.//www.cs.msu зи

в разделе «Наука» — «Работа диссертационных советов» — «Д501 00144»

МГУ.

Автореферат разослан «. апреля 2008 г.

Ученый секретарь диссертационного совета профессор

Трифонов H П

Общая характеристика работы

Актуальность темы. Значительное место в дискретной математике занимают вопросы сложности алгоритмов Центральной открытой проблемой теории алгоритмов является задача о равенстве классов сложности Р и NP Одной из наиболее исследуемых NP-полных задач является задача fc-выполнимости Для изучения «типичных» экземпляров этой задачи используется модель, когда соответствующие формулы выбираются случайным образом Дополнительный интерес к этой модели вызван существованием значительной связи с моделями статистической физики Работа посвящена исследованию некоторых свойств таких формул

Задача выполнимости состоит в том, чтобы по произвольной булевой формуле определить, является ли она выполнимой, то есть существует ли набор значений переменных, на котором формула обращается в единицу Теорема Кука гласит, что задача о выполнимости КНФ является NP-полной.1 Другими словами, задача о выполнимости лежит в классе NP и к ней полиномиально сводится любая задача из этого класса

к-котюнктивной нормальной формой (k-КНФ) называется КНФ, в которой каждая элементарная дизъюнкция состоит из не более чем к литералов (букв) Задача ¿-выполнимости — это задача о выполнимости к-КНФ Известно, что для задачи 2-выполнимости существует алгоритм с полиномиальной сложностью (то есть задача 2-выполнимости принадлежит классу Р), в то время как при к > 2 задача ¿-выполнимости NP-полна Интенсивно изучается модель, когда ¿-КНФ выбирается сл}'-чайно Задача оказалась интересной для физиков, так как она обладает свойствами, характерными для ряда физических моделей Одним из таких свойств является существование порога выполнимости

Пусть Fk(n,m) — случайная А;-КНФ, полученная путем случайного, равновероятного и независимого выбора т скобок (с повторением) из числа всех возможных скобок (элементарных дизъюнкций длины к над переменными х\, , а?„) Пусть к фиксировано, число переменных п

'CookS A, The complexity of theorem-provmg procedures, STÖG '71 Proceedings of the third annual ACM symposium on Theory of computing New York, NY, USA ACM Press, 1971 Pp 151-158

стремится к бесконечности, а число скобок m равно гп, где г — некоторая константа Верхним порогом выполнимости, называется точная верхняя грань таких г, что вероятность выполнимости формулы Ff.(n,rn) стремится к единице Нижним порогом выполнимости, г|, называется точная нижняя грань таких г, что вероятность выполнимости формулы стремится к нулю Существует предположение, что г* = г|. Такое число Гк называется порогом выполнимости

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

Утверждение 1. (Friedgut2) Для любого к > 2 существует такая последовательность rk(n), что для любого е > О

если г — (1—e)rk(n), то вероятность выполнимости Fk{n,rn) стремится к единице,

если г = (1 +s)rk(n), то вероятность выполнимости Fk{n,rn) стремится к нулю

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

Следствие. Зафиксируем к > 2 Если вероятность выполнимости формулы Fie(n, г*п) ограничена снизу положительной константой, не зависящей отп, то при г < г* вероятность выполнимости Fk(n,rn) стремится к единице

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

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

2Fnedgut, Е, Necessary and sufficient conditions for sharp thresholds of graph properties, and the h-sat problem, J Amer Math Soc, 1999, vol 12, pp 1017-1054

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

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

В середине 80-х годов Y Pu и Р Anderson впервые предположили существование значительной связи между NP-полными задачами и моделями статистической физики, такими как модель Изинга Одно из общих свойств — существование порога (фазового перехода) и резкое возрастание сложности вычислений вблизи порога Прослеживаются аналогии между задачей выполнимости случайной &-КНФ и моделями спинового стекла (материалов с неупорядоченной магнитной структурой)

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

Многие работы были посвящены оценкам порога выполнимости, как в общем случае, так и для конкретных значений к В 2004-м году D Achlioptas и Y Peres успешно применили метод вторых моментов для улучшения нижней оценки 3 Им удалось доказать, что ru ~ 2fcln2 (при к оо) Кроме того, ими были улучшены нижние оценки Гк для всех к > 3

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

Кроме порога выполнимости, с 2005-го года изучается эффект клас-

3 Achlioptas D , Peres Y, The threshold of random k-sat ts 2h In 2 - o(k), J Amer Math Soc , 2004, vol 17, pp 947-973

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

Еще одна важная характеристика множества выполняющих наборов (JVjrA(n,m)) — наличие в нем граней различных размерностей Изучение вероятности присутствия граней различных размерностей в Л/д („,„,) позволит более подробно понять структуру кластеров, а в случае, когда кластеризация не доказана (или не происходит) — позволит сделать первые конкретные выводы о структуре множества выполняющих наборов,

Цель диссертации. Целью диссертации является изучение предельных свойств случайных КНФ вблизи порога выполнимости

Задачи диссертации.

• Улучшение нижних оценок порога ¿-выполнимости

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

Научная новизна Все результаты диссертации являются новыми

1 Улучшен метод получения нижних оценок порога fc-выполнимости при к > 3, разработанный D Achlioptas и Y Peres

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

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

4 Найден метод получения нижних оценок порога присутствия граней размерности ns в Мщщтп) при к > 3

Научная и практическая ценность. Работа имеет теоретическую направленность Улучшены нижние оценки порога ^-выполнимости для к = 4,5,6,7, указан способ улучшения таких оценок для к > 7 Найден метод получения таких г к,«, что вероятность присутствия грани размерности ш в №рк(ПгГк >п) стремится к единице

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

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

Публикации и апробирование. Результаты диссертации докладывались на семинаре ВМиК МГУ «Дискретный анализ» (руководители—А А. Сапоженко, Н Н Кузюрин, В П Воронин), на семинаре ВМиК МГУ «Теория риска» (руководители — В Е Венинг, В Ю Королев, А А Кудрявцев), на VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2004 г), на XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г), на IX Международном семинаре «Дискретная математика и ее приложения» (Москва, 2007 г), а также на VI Молодежной научной школе по дискретной математике и ее приложениям (Москва, 2007 г)

По теме диссертации опубликовано б работ

Структура и объем работы. Диссертация состоит из введения, двух глав и списка литературы Объем диссертации — 77 страниц Список литературы содержит 48 наименований

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

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

В главе 1 предложена модификация метода получения нижних оценок для порога ¿-выполнимости при к > 3, который разработали D Achlioptas и Y Peres 3

В параграфе 11 приведены предыдущие известные оценки порога ¿-выполнимости для fc = 3,4,5,6,7 в сравнении с результатами первой главы

к 3 4 5 6 7

Верхняя оценка 4,51 10,23 21,33 43,51 87,88

Алгоритмическая нижняя оценка 3,52 5,54 9,63 16,78 33,32

Нижняя оценка Achlioptas, Peres 2,68 7,91 18,79 40,74 84,82

Результат первой главы 2,82 8,09 18,91 40,81 84,87

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

Лемма 1. (Метод вторых моментов) Пусть X — неотрицательная случайная величина Тогда

Р(Х>0 )>Ш1 р{Х>0>-тж)

Если X — неотрицательная случайная величина, значение которой определяется выбором формулы ^(п, гп), и при X > О КНФ выполнима, то вероятность выполнимости ^(п, гп) будет не меньше М(Х)2/М(Х2) Таким образом, если М(Х2) == О (М(Х)2) при п оо,

то rfc > г по следствию утверждения 1. D Achlioptas и У Peres исследовали применимость метода вторых моментов к различным случайным величинам В простейшем случае, когда случайная величинаXq равна числу выполняющих наборов случайной формулы, Хо = метод вторых моментов не дает результатов, поскольку M(Xo)2/M(Xq) О при п оо

Для улучшения нижней оценки порога выполнимости требуется выбрать такую случайную величину X, что из X > 0 следует выполнимость формулы, и к X применим метод вторых моментов

В параграфе 1 3 приведены рассуждения, которыми D Achlioptas и Y Peres руководствовались при выборе случайной величины Пусть W — множество действительнозначных функций видаго(<т, с), где а £ {0,1}", а с — некоторая к- буквенная скобка Рассматривается класс случайных величин

где сумма берется по всем а £ {0,1}", а произведение — по всем скобкам случайной КНФ, и Ц<т,с) е1¥

Так как переменные, входящие в формулу, выбираются равновероятно, естественно рассматривать функции вида ь){о, с) = шу(СТ1ф где с) — это число букв скобки с, обращающихся в единицу на наборе а Таким образом, функция из определяется выбором к + 1 параметров Шо, ,,Шк Метод вторых моментов применим, если из невыполнимости формулы следует X = 0 Это возможно только при щ = 0 Кроме того, равенство

является необходимым условием применимости метода вторых моментов

С учетом условия нормировки, выбор функции ш удается свести к выбору к - 2 параметров

Приведены выражения для MX и М(Х2), которые легко получаются благодаря независимости выбора скобок и линейности математического ожидания

D Achlioptas и Y Peres среди всех членов класса случайных величин X выбрали одну случайную величину, которая, по словам авторов, позволяла получить наилучшие для данного класса нижние оценки порога выполнимости, хотя строго это яе доказывалось Они выбрали

где Z и А — константы Такой выбор существенно упрощает необходимые вычисления и рассуждения,

В параграфе 1.4 метод, который применили D Achlioptas и Y Peres, обобщается с целью получения более точных нижних оценок порога выполнимости

Пусть N+ С {0,1}" — множество наборов, на которых не менее половины букв формулы обращаются в единицу

Основной вклад в М(Х2) дают наборы, на которых в единицу обращается меньше половины букв формулы Поэтому имеет смысл рассмотреть случайную величину

CTSJV+ с

Для того, чтобы оценить МХ+, доказывается следующая лемма Лемма 4. М(Х+)/М(Х) 1/2

Получено выражение для оценки сверху М(Х|) Найдена функция gr(a,ß), зависящая от параметров г, такая, что верна следу-

ющая теорема

Теорема 1 Пусть для фиксированного г существуют шЪ; г = 1, к и кусочно-постоянная функция Ь(а) > такие, что для всех а ф 1/2 выполняется неравенство #г(1/2,1) > gr(a,b(a)) Пусть кроме того g"(a, 1) < 0 при а = 1/2 Тогда г - нижняя оценка порога к-выполни-мости

Таким образом, задача получения нижней оценки порога &-выполни-мости для некоторого фиксированного к сводится к следующей задаче Нужно найти г, параметры , щ и кусочно-постоянную функцию Ь{а) > 1, чтобы выполнялось условие теоремы 1 Такую задачу можно решать численными методами

В параграфе 15с помощью теоремы 1 улучшены нижние оценки порога ^-выполнимости при к = 4,5,6,7. Значения параметров . , получены с помощью простейшего метода итеративного спуска

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

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

В параграфе 2 1 используется тот факт, что присутствие фиктивных переменных в формуле обеспечивает наличие граней в множестве ее выполняющих наборов Если у формулы есть один выполняющий набор, то присваивая фиктивным переменным всевозможные значения, получим грань, состоящую из выполняющих наборов, причем размерность грани равна числу фиктивных переменных Это число оценено с помощью метода вторых моментов в следующей теореме

Теорема 3. Пусть с — константа, с < е~кт Тогда с вероятностью, стремящейся к единице, не менее сп из переменных ®1, ., хп не войдут в формулу ^(п,гп)

Направлением грани = {(®1, , %п) € Вп хч = ,х1д —

од} называется множество {«1,. , гq} номеров координат, принимающих единственное значение в грани

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

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

Предположение. Для любого к > 2 и для любого э, 0 < в < 1, существует такое г^а, что

если г < то с вероятностью, стремящейся к единице, в Агрк(п,т) найдется грань размерности пз,

если г > г^, то с вероятностью, стремящейся к единице, в Мрк(п,т) отсутствуют грани размерности пз

Назовем такое г^ порогом присутствия граней. В параграфе 2 2 доказывается существование порога в форме последовательности для присутствия граней Для этого используется метод, который разработали Е Шес^г^ и J Вош^ат в 1999 году2 (Утверждение 4)

Леммы 5 — 9 содержат утверждения технического характера, позволяющие получить с помощью этого метода следующую теорему

Теорема 4. Для всех к > 2 и з 6 (0,1) существует такая последовательность г^)8(п), что для любого г > О

если г = (1 — е)т>1в(п), то с вероятностью, стремящейся к единице, в №щп>гп) найдется грань размерности пв,

если г = (1 + е)гь,в(п), то с вероятностью, стремящейся к единице, в отсутствуют грани размерности пв

Теорема 4 в частности означает, что верен аналог следствия утверждения 1 для граней.

Следствие. Зафиксируем в Е (0,1), г > 0, к > 3 Если вероятность присутствия в грани размерности пв ограничена снизу поло-

жительной константой, не зависящей от п, то Гк,$ > г

В параграфе 2 3 исследуется случайная величина, равная числу граней размерности пв в Мщп<Тп),

где — множество граней размерности пв п-мерного куба Рассматривается вопрос, возможно ли применить к Хо метод вторых моментов аналогично тому, как это было сделано в первой главе Получены выражения для МХо и М(Хо), и доказано, что при всех к > 3 и г > О отношение М(Хо)2/М(Хд) стремится к нулю Таким образом, в данном случае не удается применить метод вторых моментов для оценки порога присутствия граней

В параграфе 2 4, чтобы обойти проблемы, возникшие в предыдущем параграфе, обобщен подход из первой главы Пусть — множество действительнозначных функций видаш(<х, с), где а е С?", — грань размерности пз п-мерного куба, а с — некоторая скобка Рассматривается класс случайных величин

Е

с

где сумма берется по всем а € а произведение — по всем скобкам случайной формулы, и ш(а, с) £ Ш

Найден метод получения нижних оценок порога присутствия граней размерности п$ в Л^п/п) при к > 3 Точнее, найдена функция дг(а,0), зависящая от параметров г, а/1, ,и>к, такая, что верна следующая теорема

Теорема 5. Пусть г — такое, что у функции дг(а,13) есть единственный максимум в точке ^ЦгЦ — Тогда гц,я > г

Равенство

является необходимым условием того, что дг(а, 0) достигает максимума в этой точке

Таким образом, задача получения нижней оценки порога присутствия граней сводится к следующей задаче Нужно найти г и параметры

из 1, ,Шк, чтобы выполнялось условие теоремы 5 Такую задачу можно решать численными методами

В параграфе 2 5 продемонстрирована эффективность метода при к = 7 Приведены нижние оценки гт1$ для конкретных значений я, полученные с помощью теоремы 5, в сравнении с оценками, которые могут быть получены из теоремы 3

S Ю-1 ю-2 ю-3 10~4 кг®

Нижняя оценка Г7,„ теорема 3 0,32 0,65 0,98 1,31 2,96

Нижняя оценка rrlS, теорема 5 53,76 80,52 82,48 82,64 82,66

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

1 Улучшен метод получения нижних оценок порога ^-выполнимости при к > 3, разработанный D Achlioptas и Y Peres

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

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

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

Публикации по теме диссертации

1 Воробьев Ф Ю , О нижней оценке порога ^-выполнимости, VI Международная конференция «Дискретные модели в теории управляющих систем» — М Издательский отдел Факультета ВМиК МГУ им М В Ломоносова, 2004 — С 24

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

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

4 Воробьев Ф Ю , О числе выполняющих наборов случайной к-КНФ, Материалы IX Международного семинара «Дискретная математика и ее приложения» — 2007. - С 210-212

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

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

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 16 04 2008 г Формат 60x90 1/16 Услпечл 1,0 Тираж 70 экз Заказ 175 Тел 939-3890 Тел /Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы,МГУ им MB Ломоносова, 2-й учебный корпус, 627 к

Введение

I Нижняя оценка порога ^-выполнимости

§ 1 Результаты.

§ 2 Метод вторых моментов.

§ 3 Выбор случайной величины.

§ 4 Улучшенный метод.

§ 5 Применение метода.

II О присутствии граней в случайной к-КНФ

§ 1 Постановка задачи.

§ 2 Порог присутствия граней.

§ 3 Невозможность прямого применения метода вторых моментов

§ 4 Сбалансированная случайная величина.

§ 5 Применение метода.

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

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

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

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

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

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

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

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

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

Это обстоятельство привлекло внимание многих исследователей к задаче ^-выполнимости. Изучение интенсивно ведется до сих пор. Для изучения „типичных" 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. Ниже приведены правила, по которым работают эти алгоритмы, когда в формуле нет однобуквенных скобок и „чистых" переменных (входящих в формулу только без отрицания или только с отрицанием). В порядке увеличения эффективности:

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 исследовали множество формул, в которые каждая переменная входит „типичное" число раз (с учетом знака), и доказали, что гз < 4,506 (см. [27], [28]).

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

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

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

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

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

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

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

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

Теорема 1. Пусть для фиксированного г существуют w{i), г = 1, к и кусочно-постоянная функция Ь(а) > 1, такие, что для всех а ^ 1/2 выполняется неравенство gr(l/2,l) > gr(a,b(a)). Пусть кроме того g"(a, 1) < 0 при а = 1/2. Тогда г - ниэ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.Международная конференция „Дискретные модели в теории управляющих систем". — М.: Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова, 2004.— С. 24.

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

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

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

5. Воробьев, Ф. Ю. О числе выполняющих наборов случайной &-кнф / Ф. Ю. Воробьев // Материалы IX Международного семинара „Дискретная математика и ее приложения". — 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. 779788.

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. 130139.

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. 189195.

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

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.