Последние публикации по NP? = CoNP вопрос

11

Меня интересует вопрос, является ли NP равным coNP или нет. Я был бы очень признателен за советы о хороших публикациях по этой теме.

Для справки, я знаю, что этот вопрос тесно связан с вопросом о том, равен ли P NP или нет (например, если NP! = CoNP, то P! = NP).

Ура, Дерек

djkern
источник
обратите внимание на хороший P =? Обследования NP покроют это. В опросе Fortnows ACM 2009 не упоминается о coNP, но в Allender 2009 есть несколько кратких ссылок.
ВЗН

Ответы:

10

MϕπM(ϕ,π)=1ϕКука и Реккоу, опрос Крайчека или эти лекции Разборова.

Сашо Николов
источник
2

=?=?

[1] NP-жесткие наборы экспоненциально плотны, если только coNP ⊆ NP / poly. Автор Гарри Бурман, Джон М. Хичкок (2008)

[2] Отчет о состоянии дел с вопросом «Против и против» Аллендер (2009)

ВЗН
источник
2
4
coNPNP/polyΣ3P=Π3P