Мы знаем, что 3SAT ≤p 3COLOR (т.е. 3SAT является полиномиальным временем, сводимым к 3COLOR).Кто-нибудь может привести короткий аргумент, почему 3COLOR ≤p 3SAT?И приведите фактическое уменьшение Кука, показывая, что 3COLOR ≤p 3SAT Пожалуйста.
короткий ответ: так как 3SAT является NP-полной, любая проблема в NP может быть сведена к решению задачи 3SAT (или показу, что она не выполнима).Следовательно, 3COLOR <= p 3SAT. </p>
Для построения pt сокращения 3COLOR до SAT, вы можете увидеть раздел 2 в следующем документе (тема не связана с вашим вопросом):
http://research.microsoft.com/apps/pubs/default.aspx?id=66816