Theoretische informatik

Bildung & Beruf Schule
#1

Schönen Guten Tag,

ich hoffe, dass Sie mir helfen können. Ich soll beweisen, dass das Mastermind-Spiel NP-Vollständig ist. Hierzu diente mir der folgende Artikel:
http://arxiv.org/pdf/cs.CC/0512049

Alles, bis zum Beweis, war verständlich für mich, doch dann am Beweis selber stolperte ich über einige Sachen.
Da ich nicht weiß, ob Sie sich schon einmal diesen Artikel angeschaut haben oder nicht, wollte ich erstmal nachfragen, ob Sie sich schon einmal diesen Beweis angeschaut haben? Es macht ja keinen Sinn, ihnen jetzt meine Frage zu stellen, wenn Sie sich gar nicht damit auseinander gesetzt haben.
Natürlich würde ich mich sehr freuen, wenn Sie sich diesen Artikel schon einmal angeschaut haben. Ich habe leider, zwar nur eine, aber ausschlaggebende Frage für diesen Beweis, durch welchen ich leider nicht im Beweis vorankomme. :frowning:

Ich hoffe sehr, dass sie mir dabei helfen können. :smile: Das wäre dann echt supi. :smile:

Mit freundlichen Grüßen

Clodan

#2

Sorry, da bin ich schon zu lange raus…

#3

Hallo Clodan,

wie ist denn deine Frage?

Grüße
McGee

#4

Also ich verstehe bei dem Beweis nicht, wieso gilt:
l = 3 + 2*#V + E
Wieso die 3 hier drin ist, ist mir klar, doch ich verstehe nicht, wieso man 2*#V braucht. Im Artikel wird beschrieben, dass man das braucht, damit es keine Stelle gibt, an der sich ein Knoten in der Annahme und ein Knoten (der gleiche) in der Lösung überschneidet. Wieso ist das so? Das verstehe ich leider nicht. Sad
Und wozu bei der Menge von Farben das Y und N da sind, habe ich auch noch nicht so ganz raus. Ich habe dazu lediglich nur Vermutungen, also das diese eine Art Platzhalter für entweder Werte sind (Y) oder einfach nur, um das Tupel zu füllen, da ein Tupel keine leeren Elemente haben kann (N).

Hast du dich schonmal mit diesem Artikel auseinandergesetzt? Das wäre ja dann echt supi. :smile:

#5

Hast du dich schonmal mit diesem Artikel auseinandergesetzt?

Nee, den Artikel kannte ich noch nicht :smile:

Und wozu bei der Menge von Farben das Y und N da sind, habe
ich auch noch nicht so ganz raus. Ich habe dazu lediglich nur
Vermutungen, also das diese eine Art Platzhalter für entweder
Werte sind (Y) oder einfach nur, um das Tupel zu füllen, da
ein Tupel keine leeren Elemente haben kann (N).

Jup, N braucht man, um z.B. Guess (3) aufzuschreiben. Da N nicht in der Lösung vorkommt, bezieht sich der Score (0,2) eindeutig auf e_i,a,b. Die anderen Farben kann man nicht verwenden, da diese Auswirkungen auf den Score hätten.

Y ist einfach ein Lückenfüller für Stellen, die nicht verwendet werden, darf aber im Gegensatz zu N in der Lösung vorkommen.

Also ich verstehe bei dem Beweis nicht, wieso gilt:
l = 3 + 2*#V + E

Die Gleichung gilt, weil die Autoren l so definieren :smile:

Wieso die 3 hier drin ist, ist mir klar, doch ich verstehe
nicht, wieso man 2*#V braucht. Im Artikel wird beschrieben,
dass man das braucht, damit es keine Stelle gibt, an der sich
ein Knoten in der Annahme und ein Knoten (der gleiche) in der
Lösung überschneidet. Wieso ist das so? Das verstehe ich
leider nicht. Sad

Deine Frage geht in die Richtung, ob ein Beweis mit l=3+#V+E auch funktionieren würde. Müßte man ausprobieren, keine Ahnung :smile: Ein Nachteil wäre dann z.B., der Folgende:
Wenn für die Knoten nur #V Plätze zur Verfügung stehen, muss im Guess (4) der Score von (3,n) auf (3+n,0) geändert werden, womit den Knoten feste Plätze zugeweisen werden.
D.h., dass im (Only If) Absatz, würde sich die erste Gleichung nicht so schön blockweise hinschreiben lassen, sondern es müssten Y’s zwischen den Knoten stehen.

Könnte nur Kosmetik sein für einen schöneren/einfacheren Aufschrieb.

Hoffe, dass hilft Dir weiter …

#6

Hallo Clodan,

den Artikel kenne ich nicht, habe ihn nur kurz überflogen. Es ist bei mir schon etwas länger her, aber Beweise dieser Art verlaufen oft ähnlich (z.B. Beweis des Satzes von Cook verwendet auch ähnliche Methoden und mit dem hab ich mich recht ausgiebig beschäftigt). Stell doch einfach mal Deine Frage, vielleicht kann ich Dir helfen.
beste Grüße
Markus

#7

hi McGee,

supi, das hilft mir schon etwas weiter. :smile: Doch ich hätte da noch ein paar, nur kleine, Verständnisfragen. Hast du vllt. ICQ oder ein anderes Chatprogramm? Würde mich darüber freuen, ein paar noch kleine Fragen in einem Chat zu klären. :smile: Natürlich nur, wenn du auch möchtest und Zeit hast etc., da ja alles auf freiwilliger Basis basiert. :smile:
Aber vllt. ist ja dann dieser noch ein bisschen für mich mysteriöse Beweis abgeschlossen und ich wäre wieder ein bisschen schlauer und erfahrener in solchen Sachen. :smile:

#8

Nee,

schick mal als Email. Dann schau ich mir die Fragen in Ruhe an …

#9

Hi McGee,

also nochmal wegen N und Y. N und Y sind ja einfach Platzhalter für Werte. Y ist ein Platzhalter/Lückenfüller in dem Tupel, welches auch in der Lösung vorkommen darf, aber N darf nicht in der Lösung vorkommen. Was sagt denn das N genau aus? Wenn es nicht i nder Lösung vorkommen darf, wozu dient das einem? Y dient ja einem dazu, Platz für Werte zu reservieren, doch bei dem N versteh ich noch nicht zu 100%, was es mit diesem auf sich hat. Wozu dient das N? Es ist ein Platzhalter für Werte, aber was für Werte? Reservieren Y und N die gleichen Werte oder unterschiedliche? Das mit dem N und Y ist leider mein kleiens Hauptproblem, weswegen ich deswegen dann dem If und Only If nicht so ganz folgen kann. :frowning:

Wäre supi, wenn du mir bei dem N und Y noch ein bisschen näher erklären könntest, wie man die beiden so genau verstehen könnte. Deine eine Nachricht half schon sehr gut, doch zu 100% machte es leider noch nicht Klick, aber brachte mich trotzdem nach vorne. :smile:

MFG Clodan

#10

Also bei dem Beweis geht es mir darum, zu verstehen, wozu genau bei dem:
l = 3 + 2*#V + #E
das E da ist. So wie ich es verstehe, dient die #E dazu, einen Ausgleich für die Kantenannahmen zu erreichen (so übersetzte ich es), doch leider kann ich mit dieser aussage nichts anfangen. :frowning: Wieso müssen die Kantenannahmen ausgeglichen werden? Wieso genau #E? Wäre supi, wenn du hierbei eine Idee hättest, wie der autor das genau meinte. :smile:

MFG Clodan

#11

Hallo Clodan,

Es ist ein Platzhalter für Werte, aber was für Werte?

N ist keine Variable. Es ist eine Farbe im Mastermind Spiel. Die anderen Farben könne bei der Lösungsrücktransformation interpretiert werden, N und Y halt nicht.

Das N braucht man, um Guess (3) hinschreiben zu können. Ohne N geht der Beweis nicht. Ist ein Hilfskonstrukt. Du kannst ja mal N wegnehmen und schauen, was dann passiert.

Grüße
Thorsten

#12

Hallo Clodan,

den Beweis habe ich noch nie gelesen. Ich nehme an, es dürfte nicht so einfach sein, da jemanden zu finden. Viel Glück!

Gruß, Mofte