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
Respuestas:
fuente
Sam Buss tiene un bonito artículo reciente que puede leer el público en general. Es posible que desee verificarlo:
fuente
[1] Los conjuntos NP-Hard son exponencialmente densos a menos que coNP ⊆ NP / poly de Harry Buhrman, John M. Hitchcock (2008)
[2] Un informe de estado sobre la pregunta P vs NP Allender (2009)
fuente