Skip to content
Home » Post Correspondence Problem (PCP)

Post Correspondence Problem (PCP)

The Post Correspondence Problem (PCP) is an important undecidable problem in the Theory of Computation. It was introduced by Emil Post.

It is mainly used to demonstrate that some problems involving strings and matching cannot be solved by any general algorithm.


1. Definition

In PCP, we are given a finite collection of pairs of strings:\[ \left(\frac{x_1}{y_1},\frac{x_2}{y_2},\ldots,\frac{x_n}{y_n}\right) \]

The problem is to determine whether there exists a sequence of indices:\[ i_1,i_2,\ldots,i_k \]

such that:\[ x_{i_1}x_{i_2}\cdots x_{i_k} = y_{i_1}y_{i_2}\cdots y_{i_k} \]

In simple words:

Can we select some of the given pairs, possibly repeating pairs, so that the concatenated strings on the top and bottom become exactly equal?


2. Basic Structure

A PCP instance is usually represented using dominoes/cards:

   ┌───────┐
   │  x₁   │
   ├───────┤
   │  y₁   │
   └───────┘

   ┌───────┐
   │  x₂   │
   ├───────┤
   │  y₂   │
   └───────┘

   ┌───────┐
   │  x₃   │
   ├───────┤
   │  y₃   │
   └───────┘

We need to select dominoes in some order so that:

Top concatenation
       =
Bottom concatenation

3. Simple Example

Suppose the PCP instance contains:

DominoTopBottom
1aab
2baa

So we have:

1:  a
    ab

2:  ba
    a

Try sequence:\[ 1,2 \]

Top:\[ a+ba=aba \]

Bottom:\[ ab+a=aba \]

Therefore:\[ \boxed{aba=aba} \]

So the sequence 1, 2 is a solution.


4. Another Example

Consider:

DominoTopBottom
1aab
2baa

Select:

1 → 2

Top:

a + ba = aba

Bottom:

ab + a = aba

Therefore:

Top    = aba
Bottom = aba

Hence, the PCP has a solution.


5. How to Solve a PCP Instance

For a small PCP problem, we can try different sequences.

Step 1

Choose a domino.

Step 2

Compare the top and bottom strings.

Step 3

If one is a prefix of the other, continue with another domino.

Step 4

Keep adding dominoes.

Step 5

If the complete top and bottom strings become equal, a solution is found.


Example

Suppose:

No.TopBottom
1aab
2baa

Start with domino 1:

Top    = a
Bottom = ab

Top is a prefix of bottom.

Choose domino 2:

Top    = a + ba
       = aba

Bottom = ab + a
       = aba

Therefore:\[ \boxed{1,2} \]

is a solution.


6. Why Is PCP Important?

The important theoretical result is:\[ \boxed{\text{PCP is undecidable}} \]

This means:

There is no general algorithm that can determine for every possible PCP instance whether a matching sequence exists.

For some instances, we can find a solution.

But if no solution exists, there is no universal algorithm guaranteed to always finish and say:

“No solution exists.”


7. PCP and Turing Machines

PCP is closely related to Turing Machines.

It has been proved that PCP is undecidable by reducing another known undecidable problem to PCP.

The general idea is:

Known Undecidable Problem
          ↓
Transform into PCP
          ↓
If PCP were decidable
          ↓
Known problem would become decidable
          ↓
Contradiction
          ↓
PCP is undecidable

Thus PCP is an important tool for proving other problems undecidable.


8. Modified Post Correspondence Problem (MPCP)

There is also a variation called the:

Modified Post Correspondence Problem (MPCP).

The main difference is that in MPCP:

The first domino must be selected first.

PCP

Any domino can be selected first.

MPCP

A specified first domino must be selected first.

Despite this restriction, MPCP is also undecidable.


9. PCP vs MPCP

PCPMPCP
Any domino can be selected firstSpecified first domino must be selected first
No fixed starting dominoFixed starting domino
UndecidableUndecidable
Used in undecidability proofsAlso used in undecidability proofs

10. Important Properties of PCP

1. Dominoes can be reused

A pair can be selected more than once.

For example:\[ 1,2,1,1,3,2 \]

is allowed.

2. Order matters

The sequence of selected dominoes is important.

3. At least one domino is selected

A non-empty sequence is normally required.

4. Exact equality is required

The final strings must be exactly equal.

For example:

Top    = ababa
Bottom = ababa

is a match.

But:

Top    = ababa
Bottom = abab

is not a match.


11. PCP as an Unsolvable Problem

PCP belongs to the undecidable problem category.

              Unsolvable Problems
                      │
          ┌───────────┴───────────┐
          ↓                       ↓
    Halting Problem              PCP
          ↓                       ↓
     Undecidable             Undecidable

This is why PCP is included in the last unit of the TOC syllabus.


12. Difference Between Halting Problem and PCP

Halting ProblemPCP
Deals with Turing MachinesDeals with string pairs/dominoes
Question: Will TM halt?Question: Can strings be matched?
UndecidableUndecidable
Uses computation behaviorUses string concatenation
Important for computabilityImportant for undecidability proofs

13. Applications / Importance

PCP is mainly important theoretically.

It is used to:

  • Study undecidability.
  • Prove other problems are undecidable.
  • Understand limitations of algorithms.
  • Establish relationships between formal languages and computation.
  • Study decision problems involving grammars and strings.

5–10 Marks Exam Answer

Post Correspondence Problem (PCP)

The Post Correspondence Problem (PCP) is an undecidable problem introduced by Emil Post. In PCP, we are given a finite set of pairs of strings:\[ \left(\frac{x_1}{y_1},\frac{x_2}{y_2},\ldots,\frac{x_n}{y_n}\right) \]

The objective is to determine whether there exists a non-empty sequence of indices \(i_1,i_2,\ldots,i_k\) such that:\[ x_{i_1}x_{i_2}\cdots x_{i_k} = y_{i_1}y_{i_2}\cdots y_{i_k} \]

The pairs can be selected in any order and may be repeated.

For example:

No.TopBottom
1aab
2baa

Selecting \(1,2\):\[ Top=a+ba=aba \]\[ Bottom=ab+a=aba \]

Therefore, \(1,2\) is a solution.

However, there is no algorithm that can determine for every possible PCP instance whether a solution exists. Hence:\[ \boxed{\text{PCP is undecidable}} \]

A related problem, Modified PCP (MPCP), requires a specified first domino and is also undecidable.

Fast Memory Trick

PCP = Pair → Choose → Concatenate → Compare

And remember:

“Can the top and bottom strings be made exactly equal?” → PCP

PCP = Undecidable Problem