Будет ли корректна теорема Кука, если в формулировке задачи о КНФ-выполнимости слово "выполняется" заменить на "тождественно ложна"? Теорема Кука утверждает, что задача о КНФ-выполнимости является NP-полной. Исходная формулировка задачи о КНФ-выполнимости: Существует ли набор значений булевых переменных, встречающихся в формуле, при котором заданная формула (записанная в виде КНФ), выполняется ( т.е. принимает значение "истина")?

задан 21 Май 21:48

изменен 21 Май 22:44

Если Вы говорите о формулировке, то надо её привести. Даже если эти сведения стандартны, способы изложения одних и тех же вещей в разных версиях могут отличаться.

(21 Май 22:13) falcao

Я так понимаю, в случае замены формулировки нужно прежде всего иметь задачу из класса NP. Если формула выполнима, но недетерминистский алгоритм угадывает, какие именно значения переменных 0 и 1 надо подставить, чтобы формула приняла значение 1. А какое свидетельство того, что формула тождественно равна нулю, мы имеем? Как в этом убедиться за полиномиальное время недетерминистки? Это неочевидно.

Вероятнее всего, мы получим аналоги обычных теорем для класса CoNP вместо NP. Проблема совпадения этих классов в той же мере открыта, как и P=NP.

(22 Май 2:20) falcao

Благодарю за ответ, также склонялся,, что в случае замены задача перестанет быть NP-полной, и будет принадлежать к coNP. А может ли задача из NP лежать также и в coNP? Вернее, правильно ли я понимаю, что это возможно лишь в случае P=NP=coNP?

(22 Май 14:24) sallycandice

@sallycandice: может, конечно -- такова любая проблема из P. Нетривиальный пример, когда о проблеме априори не известно, что она принадлежит P, но заведомо лежит и в NP, и в coNP -- проблема факторизации. См. здесь.

(22 Май 14:40) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×237

задан
21 Май 21:48

показан
31 раз

обновлен
22 Май 14:40

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

по почте:

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

по RSS:

Ответы

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

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