Reduzierbarkeit von PCPs < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 09:52 Sa 05.07.2008 | | Autor: | Leader |
| Aufgabe | | Wir betrachten das PCP (= Post'sches Correspodence Problem) über den Alphabeten [mm] A_1 [/mm] = {a, b, c} und [mm] A_2 [/mm] = {0, 1}. Dabei bezeichnen wir diese Varianten des PCP's mit [mm] PCP(A_1) [/mm] und [mm] PCP(A_2). [/mm] Lassen sich diese Probleme aufeinander reduzieren, d.h. gilt [mm] PCP(A_2) \le PCP(A_1) [/mm] bzw. [mm] PCP(A_1) \le PCP(A_2)? [/mm] |
Hallo!
Reduzierbarkeit bedeutet ja: Gegeben zwei Mengen A, B, die Teilmenge des Alphabets S sind, so gibt es eine totale und berechenbare Funktion f: S* [mm] \to [/mm] S* mit w [mm] \in [/mm] A [mm] \gdw [/mm] f(w) [mm] \in [/mm] B.
Ich frag mich nur, wie man das jetzt auf das PCP übertragen soll. Heißt das in dem Fall, dass ich jedem Tupel von [mm] PCP(A_1) [/mm] ein Tupel von [mm] PCP(A_2) [/mm] zuweisen soll (bzw. umgekehrt)? Dann könnte ich ja sagen, weise jedem Tupel aus [mm] PCP(A_1) [/mm] das Tupel (0,0) aus [mm] PCP(A_2) [/mm] zu, dann wäre die Funktion total, berechenbar und es würde auch die Bedingung für Reduzierbarkeit gelten.
Das wiederum finde für diese Aufgabe irgendwie zu trivial. Weiß jemand, was bei der Aufgabe konkret gemeint ist bzw. wie man hier herangehen soll?
Vielen Dank.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:22 Di 08.07.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
