Семинар Добрушинской лаборатории

Когда: вторник 29 апреля, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Дарья Серова, Михаил Рыбаков (Тверской ГУ и МФТИ),
"NP-полнота задачи разбиения множества"

Задача разбиения множества (Partition) имеет очень простую формулировку, но является NP-полной. Формулировка задачи следующая: по (мульти)множеству А натуральных чисел требуется выяснить, можно ли разбить А на два подмножества с одинаковыми суммами элементов. Эту задачу можно сформулировать и как оптимизационную: для (мульти)множества А найти такое его разбиение на два подмножества, при котором модуль разности сумм элементов этих подмножеств является наименьшей из возможных.

В докладе будет показано простое доказательство NP-полноты (прежде всего, NP-трудности) задачи Partition. Для этого будет построено полиномиальное сведение к ней задачи SubsetSum (состоящей в том, что нужно установить для числового множества А и числа Т, имеется ли в А подмножество с суммой элементов, равной Т), к которой мы полиномиально сведем проблему CNF (проблему выполнимости булевых формул, находящихся в конъюнктивной нормальной форме). В оставшееся время мы докажем NP-трудность проблемы CNF, полиномиально сведя к ней проблему SAT (проблему выполнимости булевых формул в полном языке), а затем докажем NP-трудность проблемы SAT, используя идею классического доказательства Кука–Левина.


Планируется интернет-трансляция по адресу:
https://telemost.yandex.ru/j/81255480783695
Регистрируйтесь вашей фамилией, а не псевдонимом!

Страницы семинара:
https://sites.google.com/view/dobr-seminar
https://www.mathnet.ru/conf167

Адрес: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Вход в МФТИ только по пропускам или спискам. Поэтому участники БЕЗ пропусков МФТИ пришлите ЗАРАНЕЕ (до понедельника) информацию о себе и не забудьте паспорт.

#ВШМ_Добрушинский