Рассмотрим сложностной класс coNP = {L ∣ L ∈ NP}. Докажите, что если NP ≠ coNP, то P ≠ NP

задан 21 Май '17 23:02

1

Из общих соображений: если P=NP, то любая NP-задача детерминистски решается за полиномиальное время. При детерминистском алгоритме нет разницы между "да" и "нет", то есть ответ можно "инвертировать", откуда следует, что co-NP совпадает с NP (а также с P).

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

Ваш ответ

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

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

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

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

отмечен:

×242

задан
21 Май '17 23:02

показан
275 раз

обновлен
22 Май '17 0:54

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

по почте:

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

по RSS:

Ответы

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

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