PCP, ein auf E. Post zurückgehendes algorithmisches Entscheidungsproblem.

Gegeben ist hierbei eine endliche Folge von Wortpaaren (x₁, y₁), …, (x_k, y_k), wobei x_i, y_i ∈ Σ⁺ und Σ ein endliches Alphabet ist. Gefragt ist, ob es eine Folge von Indizes i₁, i₂,…, i_n ∈ {1,…, k}, n ≥ 1, gibt mit \begin{eqnarray}{x}_{{i}_{1}}{x}_{{i}_{2}}\ldots {x}_{{i}_{n}}={y}_{{i}_{1}}{y}_{{i}_{2}}\ldots {y}_{{i}_{n}}.\end{eqnarray} Das Postsche Korrespondenzproblem ist nicht entscheidbar (Entscheidbarkeit).

Es dient oft als Ausgangspunkt, um mit der Methode der Reduktion (many-one-Reduzierbarkeit) weitere Probleme, insbesondere im Bereich der formalen Sprachen und Grammatiken, als nicht entscheidbar nachzuweisen.