Diskussion:Postsches Korrespondenzproblem

Unter Sonderfälle bei "Grenzen der Entscheidbarkeit...": "Genauso wenn ein Symbol nur in den ersten oder nur in den zweiten Komponenten vorkommt" ist für sich genommen falsch! Man nehme einfach das Beispiel und füge ein weiteres Paar mit einem c in der oberen Reihe ein. Es bleibt trotzdem lösbar. Das ist nur richtig, wenn das Paar durch ein Ende zwingend benötigt wird. (in noch einem Fall? - puh ist schon spät) --macxs 03:37, 10. Feb 2012 (CET)

Laut Definition müsste K doch eigentlich eine Menge sein, (Gegeben sei eine endliche Menge P von Paaren \left(x,y\right) von Strings.) Im Beispiel heißt diese Menge jetzt natürlich K. Kann es sein das hier ein Fehler in der Schreibweise vorliegt? Oder gibt es für PCP's eine eigene Mengennotation? Weil, wenn nicht sollten dort auch Mengenklammern benutzt werden.

--alewo 02:17, 28. Feb 2006 (CET)

Ich habe die Notation etwas angepasst. Hoffentlich bleibt es einigermaßen verständlich. HeikoStamer 22:13, 28. Feb 2006 (CET)

Frage: Ich bin nicht so fit in theoretischer Informatik, aber kann vielleicht gleich ein Beispiel angegeben werden, dass man erst keine Fragen stellen braucht. Hab mich eben gefragt, ob die Indizes der Korrespondenzen mindestens einmal vorkommen müssen. Vielleicht genug Informationen angeben, dass solche Fragen erst gar nicht aufkommen?

Meiner Meinung nach sollte am Anfang des Artikels schon eine möglichst präzise Definition gegeben werden. Weiter unten können (und sollten) dann Beispiele folgen. Nun zur eigentlichen Frage: Es müssen nicht alle Indizes notwendigerweise vorkommen. Es kann gleichzeitig Lösungen geben, wo dies der Fall ist, und andere, wo nicht alle Korrespondenzen benötigt werden. Falls alle Lösungen ein bestimmtes Paar nicht benutzen, dann kann man natürlich eine kleinere Instanz (bzgl. $m$) konstruieren und sie ist sogar zur Anfangsinstanz in gewisser Weise isomorph. --HeikoStamer 20:05, 17. Apr. 2007 (CEST)

Hmm interessant wäre nun die Frage ob es überhaupt möglich ist, dass es Lösungen gibt, aber ein bestimmtes Paar in keiner Lösung vor kommt. Evtl. ist dies aber auch wieder unentscheidbar... (nicht signierter Beitrag von 134.60.71.41 (Diskussion | Beiträge) 14:43, 21. Sep. 2009 (CEST))

Soetwas gibt es natürlich, ein Beispiel: (1|1), (2|1) Da kommt in jeder Lösung nur das erste Paar vor :) ---139.18.1.5 (12:56, 5. Jan. 2010 (CET), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Unentscheidbarkeit für n >= 4

In einer meiner Vorlesungen behauptete mein Dozent, dass es vor eher kurzem ("auf jeden Fall in diesem Jahrtausend") gezeigt wurde, dass das PCP auch für n = 5 und später noch für n = 4 unentscheidbar ist, wobei n die Anzahl der 2-Tupel ("Paare") ist. Da diese Behauptung sich nicht mit der Wikipedia deckte, fing ich an nachzulesen und kam hierzu: https://arxiv.org/pdf/1312.6700.pdf Laut diesem Paper lässt sich das Halteproblem auf das PCP mit 4 Tupeln reduzieren, wodurch es auch für n = 4 unentscheidbar ist, wodurch nur noch der Fall n = 3 offen bleibt. Wenn es hilft ist hier auch noch ein Paper für den Fall n = 5: https://drops.dagstuhl.de/opus/volltexte/2015/4948/

Ich würde mich freuen wenn das jemand in den Artikel übernehmen kann. MfG laserapfel

Literatur

Die Literaturstellen [2] und [4] sind identisch, davon sollte eine entfernt werden. --2001:9E8:AF:6D00:2166:BEE6:54BF:8BB3 19:06, 4. Okt. 2022 (CEST)

Ich habe die beiden Einzelnachweise zusammengefasst. --Fomafix (Diskussion) 19:13, 4. Okt. 2022 (CEST)