Правила форума
В этом разделе
нельзя создавать новые темы. Если Вы хотите задать новый вопрос, то
не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть
удалены без предупреждения.Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса
обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть
удалена или перемещена в
Карантин, а Вы так и не узнаете, почему.
0101 |
Сведение задачи SAT к задаче о клике 08.06.2011, 12:41 |
|
18/05/09 111
|
Последний раз редактировалось 0101 08.06.2011, 12:43, всего редактировалось 2 раз(а).
Подскажите, пожалуйста, практическое описание сведения задачи выполнимости булевых формул к задаче о клике. Т.е., если задана булева формула, как определить ее выполнимость построением соответсвующего графа и поиска клик.
|
|
|
|
|
sup |
Re: Сведение задачи SAT к задаче о клике 08.06.2011, 12:58 |
|
Заслуженный участник |
|
22/11/10 1184
|
Сведение к задаче о клике имеется в книге
Кормен, Лейзерсон, Ривест Алгоритмы, построение и анализ
А уж как искать клику ...
|
|
|
|
|
0101 |
Re: Сведение задачи SAT к задаче о клике 08.06.2011, 13:15 |
|
18/05/09 111
|
Спасибо! Булева формула конкретная, может получиться хороший граф для клики.
|
|
|
|
|
|
Страница 1 из 1
|
[ Сообщений: 3 ] |
|
Модераторы: Модераторы Математики, Супермодераторы