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

• Автор: Воробьев, Федор Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 77 с.

I Нижняя оценка порога ^-выполнимости
§ 1 Результаты
§ 2 Метод вторых моментов
§ 3 Выбор случайной величины
§ 4 Улучшенный метод
§ 5 Применение метода
II О присутствии граней в случайной &-КНФ
§ 1 Постановка задачи
§ 2 Порог присутствия граней
§ 3 Невозможность прямого применения метода вторых моментов
§ 4 Сбалансированная случайная величина
§ 5 Применение метода
Список литературы

Задача выполнимости
Задача выполнимости состоит в том, чтобы по произвольной булевой формуле определить, является ли она выполнимой, то есть существует ли набор значений переменных, на котором формула обращается в единицу. Теорема Кука гласит, что задача о выполнимости КНФ является КР-полной.
^-конъюнктивная нормальная форма (/г-КНФ) — это КНФ, в которой каждая элементарная дизъюнкция состоит из не более чем к литералов (букв). Задача ^-выполнимости — это задача о выполнимости &-КНФ.
Известно, что для задачи 2-выполнимости существует алгоритм с полиномиальной сложностью (то есть задача 2-выполнимости принадлежит классу Р), в то время как при к > 2 задача ^-выполнимости КР-полна. Эта задача является одной из наиболее исследуемых ИР-полных задач. Целью диссертации является исследование некоторых числовых характеристик задачи о выполнимости случайных &-КНФ.
История вопроса
Один из первых математических результатов по алгоритмической сложности дискретных задач был получен С. В. Яблонским в 1959 г. (см. [14]) в ходе исследования алгоритмических трудностей синтеза минимальных схем. Суть результата состоит в том, что решение задачи построения бесконечной последовательности функций, имеющих сложную схемную реализацию, так называемыми „правильными“ алгоритмами непременно связано с перебором всех функций алгебры логики.
В 1962 г. в работе [8] Ю. И. Журавлев доказал, что для любого г существует такая функция, что никакой локальный алгоритм индекса г не может распознать свойство вхождения конъюнкции хотя бы в одну минимальную ДНФ.
В 1964 г. А. Н. Колмогоров ввел понятие сложности конечного объ-

екта (например, слова в некотором алфавите). Сложность определялась как минимальная длина двоичной последовательности, содержащей информацию о задаваемом объекте, достаточную для его восстановления (см. [10]).
В 1971 году С. А. Кук в своей фундаментальной работе [11] ввел определение класса ПР и доказал, что задача выполнимости является ИР-полной (теорема Кука). Другими словами, он доказал, что любая задача из класса КР полиномиально сводится к задаче выполнимости. В частности, это означает, что если существует полиномиальный алгоритм для решения задачи выполнимости, то для каждой задачи из класса № также существует полиномиальный алгоритм. Вопрос о равенстве классов сложности Р и № остается одной из центральных открытых проблем в теории сложности.
В 1972 году Р. М. Карп существенно расширил список КР-полных задач. В частности, было доказано, что задача выполнимости полиномиально сводится к задаче 3-выполнимости (см. [9]). Заметим, что список известных КР-полных задач постоянно расширяется. В то же время, задача 2-выполнимости принадлежит классу Р.
Это обстоятельство привлекло внимание многих исследователей к задаче /г-выполнимости. Изучение интенсивно ведется до сих пор. Для изучения „типичных“ /,-;-КНФ используется модель, когда формулы выбираются случайно и равновероятно из всех &-КНФ длины т над п переменными. Задача оказалась интересной для физиков, так как она обладает свойствами, характерными для ряда физических моделей. Одним из таких свойств является существование порога выполнимости.
Порог выполнимости
Будем строить случайные &-КНФ путем случайного, равновероятного и независимого выбора т скобок (с повторением) из числа всех возможных скобок (элементарных дизъюнкций длины к над переменными х, Х2 хп). Выбранную таким образом формулу будем обозначать і'Дп, га). Пусть к фиксировано, число переменных п стремится к бесконечности, а число скобок т равно гп, где г —- некоторая константа. Пусть 5Дп,г) — вероятность того, что формула .РДтг, гп) выполнима.

Теорема 4 в частности означает, что верен аналог следствия 1 для граней.
Следствие 3. Зафиксируем в £ (0,1), г > 0, к > 3. Если вероятность присутствия в Л^(1г,гп) грани размерности пв ограничена снизу положительной константой, не завися^цей отп, то г> т.
По следствию 2, грани размерности пв присутствуют в с
высокой вероятностью при 5 < е~кг. Для того, чтобы оценить эту вероятность при в > е~кг, воспользуемся методом вторых моментов. Это будет обобщением подхода, примененного в главе 1.
2.3 Невозможность прямого применения метода вторых моментов.
Как и в первой главе, будем использовать модель выбора случайных формул, когда одна переменная может встречаться в скобке несколько раз.
Естественно начать исследование применимости метода вторых моментов с рассмотрения случайной величины, равной числу граней размерности пв в Мщщгпу
^ У ^Р^(п.гп) >
где — множество граней размерности пв гг-мерного куба. Из независимости скобок и линейности математического ожидания следует, что
М(Х) = £ Р(ас МЩщгп)) = 2^-^ [П)Р(а С МРк[щгп))

- 2(1-5)" (Р(ст с Ю), (2.24)
где Ис — множество выполняющих наборов ^-буквенной скобки с.
Найдем Р(сг С ЛГС). Пусть А = {0,1, — }к — множество векторов, а — некоторая грань размерности пв. Пусть с — У х^У.. -Ух у — случайная