Дана некоторая формула. Существует ли по крайне мере два означивания переменных, при которых формула истинна? Доказать что данная задача является NP-полной.

задан 22 Сен '16 17:28

Добавим новую переменную х и домножим формулу Ф на (x V not(x)). Если Ф выполнима, то для новой формулы имеются как минимум два набора, на которых она истинна. Обратное также верно. Отсюда получается сведЕние к известной NP-полной задаче.

(22 Сен '16 22:56) falcao

Но если для новой Ф есть два набора это же не означает,что для исходной Ф имелось два набора. Сведение выполнено к задаче SAT?

(24 Сен '16 14:15) potolok

@potolok: пусть мне дали подпрограмму, которая решает задачу из условия. Тогда я умею решать SAT с её помощью. Меня спрашивают, выполнима ли формула Ф. Я строю Ф'=Ф(x V not(x)) и отдаю подпрограмме. Если Ф' выполнима на двух наборах, то на этих же наборах выполнима Ф. Если Ф' не оказывается выполнимой на двух или более наборах, это означает невыполнимость Ф. Действительно, если Ф выполнима на наборе x_1,...,x_n, то Ф' выполнима на наборах (x_1,...,x_n,x=0) и (x_1,...,x_n,x=1).

P.S. Задачи на эту тему могут быть достаточно нетривиальными, а могут быть типа "перелить из пустого в порожнее".

(24 Сен '16 15:35) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,050
×94

задан
22 Сен '16 17:28

показан
202 раза

обновлен
24 Сен '16 15:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru