Математический форум 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/ |