Minesweeper is NP-Vollständig
-
Hallo zusammen!
Zur Diskussion von P = NP oder N != NP ist mir noch eingefallen, dass es ein sogenanntes Minesweeperproblem gibt. Bei diesem wird eine leicht verändernderte Version des Computerspiels betrachtet. Das Interessante ist nun, dass man alle NP-Probleme auf Minesweeper reduzieren kann. Daher der Name: NP-Vollständig (NPV).
Für mehr Informationen, schaut unter http://www.claymath.org/Popular_Lectures/Minesweeper/.
Am Ende des Artikels gibt es auch noch weiterführende Links.
Das Tolle für mich an diesem Problem ist, dass es irgendwie zeigt, dass man Mathematik mit fast allem betreiben kann, selbst mit Dingen wie einem Computerspiel.
Liebe Grüsse,
cow_
-
Von wann ist der Artikel?
Finding the prime factors of a given integer is also widely believed to be non-P, too, but this has never been proved either.
Wurde nicht letztes Jahr bewiesen, dass man eine natürliche Zahl in n^6 (also in P) faktorisieren kann?
*weiterles*
-
Nein. Es wurde ein Algorithmus angegeben, der die Primalität einer Zahl in Polynomzeit erkennt.
Faktorisierung ist noch ein hartes Problem....zum Glück für die Krypthographie
Das mit Minesweeper ist ganz nett für die Öffentlichkeit aber für die Theorie imho wenig interessant. Gibt ja noch tausend andere NPV Probleme.
-
space schrieb:
Nein. Es wurde ein Algorithmus angegeben, der die Primalität einer Zahl in Polynomzeit erkennt.
Stimmt, danke.
-
vor 100Jahren mal auf heise
http://www.heise.de/newsticker/result.xhtml?url=/newsticker/meldung/12941&words=Minesweeper