Опишите полиномиальный алгоритм, получающий на вход булеву формулу φ, использующий оракул для языка SAT и вычисляющий выполняющее означивание для φ, если таковое существует. (Оракул для языка SAT получает на вход булеву формулу и мгновенно отвечает, является ли она выполнимой.)

задан 20 Окт '18 18:46

@Sd1: вот пример удачной и понятной формулировки с необходимыми пояснениями. В отличие от другого вопроса, где смысл понятен только узким специалистам.

(20 Окт '18 18:57) falcao
10|600 символов нужно символов осталось
0

Пусть дана формула ф(x1,...,xn). Спрашиваем оракула о выполнимости формулы ф(x1,...,x(n-1),0). Если ответ "да", то далее применяем по рекурсии тот же алгоритм к формуле с меньшим числом переменных. Если ответ "нет", то берём формулу ф(x1,...,x(n-1),1). Она выполнима, если выполнима исходная формула. К ней применяем тот же алгоритм по рекурсии, запоминая значение x(n). Очевидно, что этот алгоритм по сложности полиномиален от n.

ссылка

отвечен 20 Окт '18 19:02

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

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

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

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

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

отмечен:

×207
×128
×55

задан
20 Окт '18 18:46

показан
148 раз

обновлен
20 Окт '18 19:02

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

по почте:

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

по RSS:

Ответы

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

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