Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Entscheidbarkeit vom Postschen Korrespondenzproblem mit Teilworten gleicher Länge
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Entscheidbarkeit vom Postschen Korrespondenzproblem mit Teilworten gleicher Länge
rapiz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-08-17


Aufgabe:

Bleibt PKP unentscheidbar für eine Instanz ((x1, ..., xn),(y1, ..., yn)) der Form: |x1| =
|y1| = |x2| = |y2| = ... = |xn| = |yn|?

Lösung:
Nein, da wir prüfen können, ob es einen passenden Index mit übereinstimmenden
Worten gibt und dann eine Indexfolge der Länge 1 gefunden haben. Falls kein
Index existiert, dann gibt es keine Lösung.


Mir ist leider nicht ersichtlich, warum PKP dadurch entscheidbar wird.
Wir können zwar prüfen ob alle Längen gleich sind, jedoch impliziert dies doch noch nicht, dass eine Lösung vorhanden ist?

Diese müssen ja trotzdem noch eine PKP-Instanz bilden.
Hat jemand einen Erklärungsansatz dazu?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2008
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-17


Hallo rapiz,

wie die Prüfung auf die Lösung aussieht, hast du doch selbst hingeschrieben:

Nein, da wir prüfen können, ob es einen passenden Index mit übereinstimmenden
Worten gibt und dann eine Indexfolge der Länge 1 gefunden haben. Falls kein
Index existiert, dann gibt es keine Lösung.

Im allgemeinen müsste man für eine Entscheidung des PKP als erstes prüfen, ob es einen Index i gibt, so dass <math>x_i</math> ein Anfangsstück von <math>y_i</math> ist oder umgekehrt (falls es einen solchen Index nicht gibt, hat die PKP-Instanz auch keine Lösung; falls es einen gibt, müsste man weitermachen). Hier fängt man genau so an; aber wenn man so einen Index i findet, ist man damit schon fertig, weil <math>x_i</math> und <math>y_i</math> gleich lang sind und damit bereits gleich sein müssen.

Viele Grüße

Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]