Was noch zu beweisen wäre

dotnetpro hat in Ausgabe 7/2009 die Frage gestellt, ob die Komplexitätsklassen P und NP äquivalent sind. Diese Frage ist nach wie vor unbeantwortet – und nach wie vor sind auf diese Antwort 1 Million Dollar ausgeschrieben. Alles, was Sie für diese Summe tun müssen, ist, eine polynomiale Lösung für ein beliebiges NP-vollständiges Problem finden. Damit Sie wissen, worauf Sie sich einlassen, stellt dotnetpro in dieser Ausgabe zehn NP-vollständige Probleme vor.

Jetzt 1 Monat kostenlos testen!