Дискретные функции и выполнимость ограничений

Обязательный курс для студентов 518/1 группы магистерской программы "Дискретные структуры и алгоритмы".

Спецкурс для студентов магистратуры.

Лекции - 2 ч в неделю.

Семинары - 1 ч в неделю (для студентов 518/1 группы).

Аннотация. Цель курса - показать, каким образом теория дискретных функций применяется при решении задачи обобщенной выполнимости. Задача обобщенной выполнимости, или выполнимости ограничений (англ. constraint satisfaction problem, CSP) состоит в выяснении выполнимости системы отношений, взятых из заранее известного множества S и связывающих произвольные переменные. При этом полагается, что в S входят отношения над конечным множеством A, |A| = k. В курсе показывается, что вычислительная сложность задачи S-выполнимости зависит только от функций, сохраняющих все отношения из S. Первая часть курса посвящена булевой выполнимости (k = 2). В ней рассматривается теорема Шефера о дихотомии вычислительной сложности задачи булевой выполнимости. Вторая часть курса посвящена задаче S-выполнимости для произвольных конечных k > 2. Доказываются случаи NP-полноты этой задачи, а также рассматриваются ее полиномиальные случаи. Приводится теорема о дихотомии вычислительной сложности задачи S-выполнимости для произвольных конечных k.

Лектор - Селезнева Светлана Николаевна

Лекции

Лекция 1. Функции алгебры логики. Формулы и функции, определяемые формулами. Замкнутые классы и полные системы.

Лекция 2. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения.

Лекция 3. Полиномы Жегалкина. Линейная конъюнктивная нормальная форма (ЛКНФ), представимость ЛКНФ.

Упражнения

Занятие 1. Сокращенная КНФ и способы ее построения.

Занятие 2. Полином Жегалкина. ЛКНФ и представимость ЛКНФ.

Занятие 3. Классы P и NP, NP-полнота.

Программа курса

• Функции алгебры логики. Конъюнктивные и дизъюнктивные нормальные формы (КНФ и ДНФ). Сокращенная КНФ и способы ее построения. Полиномы Жегалкина, быстрый способ построения полинома Жегалкина функции. Линейные конъюнктивные нормальные формы (ЛКНФ). Проверка представимости функции ЛКНФ.

• Задачи распознавания свойств. Классы P и NP. Полиномиальные, NP-трудные и NP-полные задачи. NP-полнота задач распознавания выполнимости КНФ (ВЫП) и 3-КНФ (3-ВЫП), полиномиальность задачи распознавания выполнимости 2-КНФ (2-ВЫП). Постановка задачи обобщенной выполнимости S-ВЫП.

• Слабо положительные, слабо отрицательные и биюнктивные КНФ и слабо положительные, слабо отрицательные и биюнктивные функции алгебры логики. Критерии слабой положительности, слабой отрицательности и биюнктивности функции. Полиномиальность распознавания выполнимости слабо положительной, слабо отрицательной и биюнктивной КНФ.

• Линейные и мультиаффинные функции алгебры логики. Приведенное представление мультиаффинной функции алгебры логики. Критерий мультиаффинности функции. Полиномиальность распознавания выполнимости конъюнкции приведенных представлений мультиаффинных функций.

• Условная выразимость функций алгебры логики, леммы об условной выразимости функций (о транзитивности, о замене множителя в конъюнктивной форме, о подстановке констант вместо переменных и о навешивании отрицаний над переменными). Лемма о функции, сохраняющей константу 0, и функции, не сохраняющей константу 1. Лемма о функции, не являющейся четной. Лемма о функции, не являющейся слабо положительной, и функции, не являющейся слабо отрицательной. Леммы о небиюнктивной функции и немультиаффинной функции. Теорема разделимости Шефера о сложности задачи обобщенной выполнимости S-ВЫП.

• NP-полнота задач распознавания слабой положительности, слабой отрицательности, биюнктивности и мультиаффинности функции алгебры логики, заданной в виде ДНФ. Нижняя единица функции. Лемма о нахождении всех нижних единиц функции алгебры логики по ее полиному Жегалкина. Полиномиальность задачи распознавания монотонности функции алгебры логики, заданной в виде полинома Жегалкина. Лемма о числе сомножителей в приведенном представлении мультиаффинной функции. Полиномиальность распознавания мультиаффинности функции алгебры логики, заданной в виде полинома Жегалкина.

Программа семинарских занятий

Семинар 1. Повторение.

1. Построить сокращенную ДНФ данной функции алгебры логики по ее ДНФ или по ее КНФ.

2. Быстрым способом построить полином Жегалкина данной функции алгебры логики.

Семинар 2. Поляризованные полиномиальные формы (ППФ).

1. Быстрым способом построить ППФ по заданному вектору поляризации для данной функции алгебры логики.

2. Построить классификацию всех функций алгебры логики, зависящих от 2-х переменных, по длине в классе ППФ.

3. Построить классификацию всех функций алгебры логики, зависящих от 3-х переменных, по длине в классе ППФ.

Семинар 3. Полиномиальные нормальные формы (ПНФ).

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

2. Найти точную оценку длины функций алгебры логики, зависящих от 2-х переменных, в классе ПНФ.

3. Найти точную оценку длины функций алгебры логики, зависящих от 3-х переменных, в классе ПНФ.

Семинар 4. Конъюнктивные нормальные формы.

1. Выяснить, является ли заданная элементарная дизъюнкция имплицентой или простой имплицентой данной функции алгебры логики.

2. Построить сокращенную КНФ заданной функции алгебры логики по ее ДНФ или по ее КНФ.

Семинар 5. Слабо положительные, слабо отрицательные и биюнктивные функции.

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

2. Построить приведенное представление данной слабо положительно, слабо отрицательной или биюнктивной функции.

Семинар 6. Мультиаффинные функции.

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

2. Построить приведенное представление данной мультиаффинной функции.

Семинар 7. Теорема разделимости Шефера.

1. Выяснить для заданного множества S функций алгебры логики, является задача S-ВЫП полиномиальной или NP-полной.

Экзамен

Экзамен устный. В билете 2 вопроса и задача. Подготовка к ответу на билет - 1 ч.