Сегодня экзамен, знаю ответы на все вопросы, которых там около 120, кроме этих трёх, помогите, пожалуйста

  • Наболее краткий алгоритм вычисления выполнимости для 2-КНФ
  • Алгоритм сведения задачи SAT для n-КНФ к задаче SAT для 3-КНФ (тоже как можно более краткий)
  • Любая КНФ может быть преобразована в эквивалентную ДНФ, сложность задачи выполнимости ДНФ полиномиальная, следует ли отсюда, что SAT∈P? (И почему?)

Прошу помочь, крайне необходимо!

P.S. В википедии нашёл вот что:

Требование о записи в конъюнктивной форме существенно, так как, например, задача SAT для формул, представленных в дизъюнктивной нормальной форме, тривиально решается за линейное время в зависимости от размера записи формулы (для выполнимости формулы требуется только наличие хотя бы одной конъюнкции, не содержащей одновременно x и NOT x для некоторой переменной x).

Судя по всему, ответ на третий вопрос "нет", и эта реплика обосновывает?

задан 11 Янв '16 3:56

изменен 11 Янв '16 4:16

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×828
×522
×229
×142
×66

задан
11 Янв '16 3:56

показан
846 раз

обновлен
11 Янв '16 4:16

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

по почте:

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

по RSS:

Ответы

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

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