Введение 3
Постановка задачи 4
1. Обзорный раздел 5
1.1. Мотивация 5
1.2. Результаты 6
1.3. Методы 7
1.4. Ранние работы 7
2. Основные понятие 8
2.1. Вычисление булевой функции с помощью КНФ 8
2.2. Функция четности 8
2.3. Кодировка булевой функции с помощью КНФ 9
2.4. Булева схема и преобразование Цейтина 10
2.5. Схемы глубины 3 10
3. Нижние оценки на КНФ-кодировки функции четности 14
3.1. Ограниченное количество дополнительных переменных . . . 14
3.2. Ширина дизъюнктов 18
3.3. Неограниченное количество дополнительных переменных . 18
Заключение 24
Список литературы 25
Многие годы ученые в области компьютерных наук придумывают алгоритмы для ускорения решения различных задач. В теории сложности существует иерархия классов, основными представителями которой являются классы P и NP. Класс P — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время. Класс NP — класс языков (задач), ответ на который можно проверить за полиномиальное время. Вопрос о равенстве классов P и NP — это одна из центральных открытых проблем теории алгоритмов [2]. Каноническим представителем класса NP является задача выполнимости булевой формулы в конъюктивно-нормальной форме (КНФ). Несмотря на теоретическую сложность этой задачи, современные солверы работают очень быстро. К задаче выполнимости на практике сводятся огромное количество других задач. При этом сведении размер задачи может экспоненциально увеличиться. В связи с этим, возникает вопрос минимизации количества клозов при кодировки функций в виде КНФ.
Минимальное число клозов в КНФ представлении функции четности х1 ф х2 ф • • • ф xn - это 2n-1. Можно получить более компактную КНФ- кодировку, используя дополнительные переменные. В этой работе доказаны следующие нижние оценки, которые почти совпадают с известными верхними, на число m клозов и максимальную ширину к клозов: 1) если есть не больше s дополнительны переменных, то m > Q (2n/(s+1) /п) и к > n=(s + 1); 2) минимальное число клозов - хотя бы 3n.
