Postsches Correspondenzproblem

Question 1

Definition PCP

Answer 1

Eine Instanz des PCP besteht aus einer endlichen Menge K = { [x1/y1],… [x_k/y_k]} wobei x1, …x_k und y1, … y_k nichtleere Wörter über einem endlichen Alphabet Σ sind. Das Problem besteht darin, zu entscheiden, ob es eine correspondierende Folge von Indizes in {1, …, k} gibt, sodass x_i1 … x_i_n = y_i1 . … y_i_n.

Question 2

Definition Modifiziertes PCP(MPCP)

Answer 2

Eine Instanz des PCP besteht aus einer endlichen Menge K = { [x1/y1],… [x_k/y_k]} wobei x1, …x_k und y1, … y_k nichtleere Wörter über einem endlichen Alphabet Σ sind. Das Problem besteht darin, zu entscheiden, ob es eine correspondierende Folge von Indizes mit i1=1 gibt, sodass x_i1 … x_i_n = y_i1 . … y_i_n.

Question 3

Das PCP ist… (entscheidbar/semi-entscheidbar/unentscheidbar)

Answer 3

unentscheidbar

Question 4

Ordnen Sie die Reduktionen von MPCP, PCP und H.

Answer 4

MPCP ≤ PCP und PCP ≤ H, also H ≤ PCP

Question 5

Wenn alle Wörter auf den Dominos Länge 1 haben, so ist PCP …

Answer 5

entscheidbar

Question 6

Wenn alle Wörter auf den Dominos Länge 1 oder 2 haben, so ist PCP…

Answer 6

unentscheidbar

Question 7

Für 1 Domino PCP ist…

Answer 7

trivial

Question 8

Für 2 Dominos PCP ist…

Answer 8

entscheidbar

Question 9

Für 5 oder ≥ 7 Dominos PCP ist…

Answer 9

unentscheidbar