Postsches Korrespondenzproblem

Question 1

Postsches Korrespondenzproblem - Definition

Answer 1

Question 2

Wofür wir PCP oft benutzt

Answer 2

In Unentscheidbarkeitsbeweisen mit Reduktion

Question 3

Ist PCP entscheidbar?

Answer 3

nein

Question 4

ist PCP semi-entscheidbar?

Answer 4

Ja, für beliebige Sigma (vermöge Brute-Force-Algorithmus)

Question 5

ist ein “unäres PCP” (|Sigma| = 1) entscheidbar?

Answer 5

Ja

Question 6

Was sind die Genzen von Eingabepaaren k, so das PCP entscheidbar / unentscheidbar ist.

Answer 6

entscheidbar für k = 2, unentscheidbar für k >= 4.

Question 7

Ist PCP entscheidbar, falls nur nach einer Lösung mit Länge <= n gesucht wird?

Answer 7

Ja

Question 8

Zurückführung von Sigma auf Sigma’ = {0, 1}

Answer 8

Für beliebiges Sigma lässt sich PCP auf PCP mit Sigma’ = {0, 1} zurückführen.

Question 9

Modifizierte PCP: MPCP

Answer 9

Question 10

MPCP und PCP - Lemma

Answer 10

MPCP <= PCP

Question 11

MPCP - Kollar

Answer 11

H_0 <= MPCP

Question 12

Entscheidbarkeit von PCP und MPCP

Answer 12

PCP und MPCP sind unentscheidbar

Question 13

Semi-entscheidbarkeit von H_0

Answer 13

H_0 ist semi-entscheidbar