 Mastermindproblem ist NP-vollständig |
Clodan
Grünschnabel
Dabei seit: 16.11.2010
Beiträge: 1
 |
|
 Mastermindproblem ist NP-vollständig |
     |
Moin Leute!
Also ich habe eine Frage bzgl. des Mastermindsproblems:
Also Mastermind ist ja NP-vollständig, da es auf SAT zurückgeführt werden kann. Mein Professor meinte, dass es keinen Sinn macht, Mastermind auf NP-vollständig zu untersuchen, wenn man beispielsweise 5 Plätze hat (man kann also 5 Kugeln in einer Reihe platzieren) und man darf Farben in einer Reihe doppelt verwenden (d.h. in einer Reihe ist 2x rot oder 3x blau). Mit Reihe meine ich waagerechte Platzierung der Kugeln d.h. in der Matrixsprechweise eine Zeile.
Wieso macht das keinen Sinn? Ist es denn, wenn in einer Reihe Farben doppelt auftreten können, nicht mehr NP-vollständig bzw. nicht mehr auf SAT zurpckführbar oder was versteckt sich hinter dieser Aussage? O.o?
Wäre supi, wenn mir jemand bei dieser Frage helfen könnte, da ich dachte, dass die Problematik mit NP-vollständig und SAT verstand. 
Doch leider macht mir das Mastermind-Problem einen Strich durch die Rechnung, dass ich irgendwas noch nicht verstand. Deswegen wäre es wirklich schön, wenn mich diesbezüglich jemand aufklären könnte. 
MFG Clodan
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Clodan: 16.11.2010 08:30.
|
|
16.11.2010 08:29 |
|
|
|
