Was kostet die Welt: ich zahle einen Pfennig für jede
(mit nachvollziehbarer Begründung)
aus der zweiten Liste entfernte Instanz.
Bitte bereinigte Listen per mail an mich schicken,
ich veröffentliche sie dann hier.
Teilaufgabe: automatische Beweise durch unendlichen Abstieg
Unlösbarkeit von [(0,001),(10,0),(001,1)] folgt so (oder so ähnlich):
von rechts ist 1101 Pflicht, aber von links verboten.
Finde solche Zeichenketten, und die dazu passenden Beweise!
Teilaufgabe: Stark wachsende Familien
Gibt es eine Folge von PCP(3,n), deren kürzesten Lösungen
stärker als O(n*n) wachsen? Auch hier winkt ein Preis.