P = NP: ¿Cuáles son los métodos más prometedores?

Question

Sé que P = NP no ha sido resuelto hasta ahora, pero alguien me puede decir algo sobre lo siguiente: ¿Cuáles son actualmente el / la computadora matemática más prometedores científica métodos que podría ser útil frente a este problema? O son conocidos allí incluso ninguno de tales métodos a ser potencialmente útiles hasta ahora? ¿Hay alguna (gratis) compendio sobre este tema donde puedo encontrar todo / la mayor parte de la investigación realizada en esta área?

Answer 1

Una excelente visión general apareció el año pasado en Comunicaciones de la ACM. Creo que se convirtió en el artículo más descargado de CACM nunca, por lo que su pregunta puede ser relevante después de todo: -)

el estado de la P = NP Problema , Lance Fortnow, Comunicaciones de la ACM, Vol. 52 No. 9, 2009