This flashcard is just one of a free flashcard set. See all flashcards!
62
Beweis: MPKP 
PKP
PKPDefiniere Funktion die Eingaben des MPKP auf Eingaben des PKP abbildet:
auf 
Führe Sonderzeichen #, $ ein, die nicht im Alphabet von MPKP enthalten sind
Füge nach jedem
ein # ein
Füge vor jedem
ein # ein
Füge Startdomino
ein
Füge Schlussstein
ein
=> k Steine für MPKP, f(k) hat zwei Steine mehr
=> jede f(k) muss mit $ | #$ aufhören: egal was man legt, man muss oben mit # aufhören und unten mit nicht-# aufhören
=> jede Lösung muss mit Startdomino beginnen: einzige Möglichkeit oben mit # anzufangen
auf Führe Sonderzeichen #, $ ein, die nicht im Alphabet von MPKP enthalten sind
Füge nach jedem
ein # einFüge vor jedem
ein # einFüge Startdomino
einFüge Schlussstein
ein=> k Steine für MPKP, f(k) hat zwei Steine mehr
=> jede f(k) muss mit $ | #$ aufhören: egal was man legt, man muss oben mit # aufhören und unten mit nicht-# aufhören
=> jede Lösung muss mit Startdomino beginnen: einzige Möglichkeit oben mit # anzufangen
