Das P=NP-Problem ist der heilige Gral der theoretischen Informatik, auf seine Lösung hat das Clay-Institut ein Preisgeld von 1 Million Dollar ausgesetzt. Es fragt, ob jedes von einer nichtdeterministischen Turingmaschine in polynomieller Zeit lösbare Problem auch von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden kann. Ein gestern von Norbert Blum, Informatikprofessor an der Universität…
Letzte Kommentare