2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сведение задачи SAT к задаче о клике
Сообщение08.06.2011, 12:41 
Подскажите, пожалуйста, практическое описание сведения задачи выполнимости булевых формул к задаче о клике.
Т.е., если задана булева формула, как определить ее выполнимость построением соответсвующего графа и поиска клик.

 
 
 
 Re: Сведение задачи SAT к задаче о клике
Сообщение08.06.2011, 12:58 
Сведение к задаче о клике имеется в книге

Кормен, Лейзерсон, Ривест
Алгоритмы, построение и анализ

А уж как искать клику ...

 
 
 
 Re: Сведение задачи SAT к задаче о клике
Сообщение08.06.2011, 13:15 
Спасибо! Булева формула конкретная, может получиться хороший граф для клики.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group