PCP@HOME (beendet)

(Beschreibung von der Webseite des Projekts): PCP steht für Post's Correspondence Problem. Es handelt sich hierbei um ein Problem der theoretischen Informatik, welches 1946 von Emil Post in Bull. Amerc. Math. Soc. 53 veröffentlicht wurde. Er bewies die Unentscheidbarkeit im allgemeinen Fall und führte damit erstmals eine Klasse von konkreten Problemen ein, die mit dem herkömmlichen Turing-Berechenbarkeitsmodell nicht gelöst werden konnten.

Das PCP ist nun wie folgt definiert:
Sei eine endliche Folge von Wortpaaren ((p₁, q₁), (p₂, q₂), ... , (p_M, q_M)) mit p₁, q₁, p₂, q₂, ..., p_M, q_M aus {0,1}⁺ gegeben. Wir bezeichnen eine Folge von Indizes i₁, i₂, ..., i_N als Lösung der Länge N, falls p_i1 p_i2 ... p_iN = q_i1 q_i2 ... q_iN.

Dieses allgemeine Problem kann in vielerlei Hinsicht eingeschränkt werden. Dabei ergeben sich neue Problemklassen. Betrachtet man z.B. die Anzahl der Paare M, so kann man für M = 1 und M = 2 das PCP entscheiden; bzw. für M >= 7 ist die Unentscheidbarkeit bewiesen. Wir nennen M hier Größe des PCP. Für die Größe 3 <= M <= 6 ist die Frage nach der Entscheidbarkeit bis heute offen. Auf diesem Gebiet wollen wir uns nun bewegen. Dazu schränken wir auch noch die Länge der Wörter p₁, q₁, p₂, q₂, ..., p_M, q_M durch die obere Schranke Weite ein.

Ziel dieses Projektes ist es, möglichst kurze PCPs zu finden, die aber eine recht lange minimale Lösung haben. An solchen Problemen werden vielleicht Schwierigkeiten sichtbar, welche zu allgemeinen Entscheidungsstrategien für eingeschränkte PCP-Klassen führen.

Wer diese Beschreibung jetzt nicht auf Anhieb verstanden hat, sollte sich mal das PCP-Puzzle auf der Projektseite anschauen, dabei wird der Sachverhalt sofort klar.

Projektübersicht

PCP@HOME
Name	PCP@HOME
Kategorie	Mathematik
Ziel	Finden kurzer PCPs mit langen minimalen Lösungen
Kommerziell	nein
Homepage	ehemals: www.theory.informatik.uni-kassel.de/~stamer/pcp/

Dieses Projekt wird in Deutschland durchgeführt.

Projektstatus

Projektstatus
Status	beendet
Beginn	mitte 2001
Ende	Unbekannt

Clientprogramm

Betriebssysteme

	Windows
	Linux
	DOS
	BSD
	Solaris
	Java (betriebssystemunabhängig)

Client-Eigenschaften

Funktioniert auch über Proxy
Normal ausführbares Programm
Als Bildschirmschoner benutzbar
Kommandozeilenversion verfügbar
Personal Proxy für Work units erhältlich
Work units auch per Mail austauschbar
Quellcode verfügbar
Auch offline nutzbar
Checkpoints

Besonderheiten des Clients

Das Programm generiert zufällige PCPs und versucht, sie zu lösen. Dabei kann mit Hilfe einiger Parameter die Größe des benutzten Hauptspeichers sowie die maximale Lösungslänge eingeschränkt werden.

Das Ergebnis der Berechnung muss man selbst per Hand (oder mit Hilfe eines auf der Webseite verfügbaren Skripts) noch einmal auf die besten Kandidaten hin untersuchen und kann diese dann per Mail unter Angabe seines Namens einsenden.

Veröffentlichte Versionen

• 30.11.1999: 0.02