P = NP: Quelles sont les méthodes les plus prometteuses?

Question

Je sais que P = NP n'a pas été résolu jusqu'à présent, mais quelqu'un peut-il me dire quelque chose au sujet de ce qui suit: Quels sont actuellement les plus prometteuses méthodes scientifiques mathématique / informatique que pourrait être utile résoudre ce problème? Ou y at-il même aucune de ces méthodes connues pour être potentiellement utile jusqu'à présent? Y at-il (gratuit) recueil sur ce sujet où je peux trouver tous / la plupart des recherches effectuées dans ce domaine?

Answer 1

Une excellente vue d'ensemble est apparu l'année dernière dans les communications de l'ACM. Je pense qu'il est devenu l'article le plus téléchargé CACM jamais, votre question peut être pertinente après tout: -)

le statut du P = NP problème , Lance Fortnow, Communications de l'ACM, Vol. 52 n ° 9, 2009