Математический форум Math Help Planet
http://mathhelpplanet.com/

Полиномиальные сведения и NP-полные задачи
http://mathhelpplanet.com/viewtopic.php?f=44&t=66673
Страница 1 из 1

Автор:  akipol [ 29 сен 2019, 20:17 ]
Заголовок сообщения:  Полиномиальные сведения и NP-полные задачи

Первая задача: существует ли означивание переменных заданной 3-КНФ, при котором в каждой скобке окажется хотя бы один истинный и хотя бы один ложный литерал?
Вторая задача: существует ли в заданном неориентированном графе (без весов) разрез, размер которого не менее заданного числа?
Докажите, что первая задача полиномиально сводима ко второй.

Для доказательства NP-полноты можно использовать NP-полноту следующих задач: 1) выполнимость булевой формулы (SAT); 2) выполнимость 3-КНФ; 3) существование клики заданного размера в графе; 4) существование вершинного покрытия заданного размера в графе; 5) наличие гамильтонова пути в ориентированном графе.

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/