Publicaciones recientes sobre NP? = Pregunta coNP

11

Estoy interesado en la pregunta de si NP es igual a coNP o no. Agradecería mucho algunos consejos sobre buenas publicaciones para leer sobre el tema.

Para el registro, sé que esta pregunta está íntimamente relacionada con la pregunta de si P es igual a NP o no (de modo que si NP! = CoNP entonces P! = NP).

Saludos, Derek

djkern
fuente
nota alguna buena P =? Las encuestas de NP cubrirán esto. La encuesta de Fortnows ACM 2009 no menciona coNP pero Allender 2009 tiene algunas referencias breves.
vzn

Respuestas:

10

MϕπM(ϕ,π)=1ϕpor Cook y Reckhow, la encuesta de Krajicek, o estas notas de lectura de Razborov.

Sasho Nikolov
fuente
7

NPcoNPcoNP

Sam Buss tiene un bonito artículo reciente que puede leer el público en general. Es posible que desee verificarlo:

Kaveh
fuente