Изменения

Перейти к: навигация, поиск

Обсуждение:Заглавная страница

2323 байта убрано, 12:54, 14 ноября 2018
Форум: новая тема
Что-то тут не так. Мне кстати последний вариант больше нравится.
== 2-SAT Выполнимость Форум ==
Рассмотрим функцию, записанную в виде 2А есть ли на этой вики какое-КНФ (КНФ Крома). <br> 2-SAT выполнимость данной функции - эта задача распределения аргументов таким образом, чтобы результат данной функции был равен 1.  == Алгоритм решения ==  Рассмотрим любой дизъюнкт функции: (a || b) <br>Несложно заметить, что это равнозначно записи !a => b и !b => a <br> Построим ориентированный граф, где вершинами будут аргументы и их отрицание, а ребрами будут ребра вида: !a => b и !b => a для каждого дизъюнкта функции (a || b) <br> Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы то центральное место для любой переменной x из вершины x нельзя достичь !x и из вершины !x нельзя достичь x одновременно. (!x => x && x => !x) == Доказательство == Пусть 2-SAT имеет решениеобсуждений? Есть пара вопросов. <br>ДокажемВ частности, что не может быть такого, чтобы для любой переменной x из вершины x можно достичь !x установить ли расширение FlaggedRevisions и из вершины !x можно достичь x одновременно. (!x => x && x => !x) <br>Тогда чтобы из !x достичь x (!x => x) x было верным, x должен быть равен 1. С другой стороны для того, чтобы из x достичь !x (!x => x) было верным, x должен быть равен 0. Отсюда следует противоречие. <br> <br> Пусть для любой переменной x из вершины x нельзя достичь !x и из вершины !x нельзя достичь x одновременно. <br>Докажем, что этого достаточно, чтобы 2гаджет HotCat? --SAT имело решение. <br>Пусть из !x можно достичь x, но из вершины x нельзя достичь !x. Докажем, что из x не достижимо такой y, что из y достижимо !y. [[Участник:Infovarius|Infovarius]] (т.е. x => y => !y. (x = 1, y = 0)). <br>Если из x => y, то (!x [[Обсуждение участника:Infovarius|| yобсуждение]])12:54, отсюда следует (!y => !x). Тогда x => y => !y => !x. Следовательно x => !x. Противоречие.  == Источники == MAXimal :: algo :: Задача 2-SAT 14 ноября 2018 (2-CNFMSK) <ref> http://e-maxx.ru/algo/2_sat </ref>
202
правки

Навигация