задан 28 Май '17 3:12

10|600 символов нужно символов осталось
1

Если формула выполнима, то существует выполняющая оценка. Проверка того, что она подходит, занимает полиномиальное (линейное) время. Следовательно, задача нахождения такой оценки (если она есть), принадлежит классу NP. Если P=NP, то для этой же задачи имеется детерминистский алгоритм, решающий её за полиномиальное время. Допустим, что ответ отрицателен -- тогда всё сделано. При положительном ответе остаётся найти выполняющую оценку. Полагаем первую переменную x1 равной 0, подставляем в формулу. Проверяем её при помощи того же полиномиального алгоритма на выполнимость. В случае положительного ответа оставляем значение x1=0, в случае отрицательного берём x1=1. Формула с выбранным значением x1 выполнима, и далее то же делаем с переменной x2. За n шагов мы найдём выполняющую оценку, а время работы алгоритма останется полиномиальным, будучи умноженным на O(n).

ссылка

отвечен 28 Май '17 6:35

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×416
×154
×31

задан
28 Май '17 3:12

показан
371 раз

обновлен
28 Май '17 6:35

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

по почте:

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

по RSS:

Ответы

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

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