Меня интересует вопрос, является ли NP равным coNP или нет. Я был бы очень признателен за советы о хороших публикациях по этой теме.
Для справки, я знаю, что этот вопрос тесно связан с вопросом о том, равен ли P NP или нет (например, если NP! = CoNP, то P! = NP).
Ура, Дерек
Ответы:
источник
У Сэма Бусса есть хорошая недавняя статья, которая читается широкой аудиторией. Вы можете проверить это:
источник
[1] NP-жесткие наборы экспоненциально плотны, если только coNP ⊆ NP / poly. Автор Гарри Бурман, Джон М. Хичкок (2008)
[2] Отчет о состоянии дел с вопросом «Против и против» Аллендер (2009)
источник