PCP & MPCP

PCP(Post's Correspondence Problem)

MPCP(Modified PCP)

PCP consists of two lists A=w1,....,wk and

B=x1,....,xk , of strings over some alphabets SIGMA.

This instance of PCP has a solution if there is any sequence of integers i1,i2,.....,im,with m>=1. Such that

wi1,wi2,....,wim=xi1,xi2,....,xim.

The sequence i1,....,im is a solution to this instance of PCP.

MPCP 

Lists A & B of k strings each from Sigma*.say

A=w1,w2,...,wk

and

B=x1,x2,.....,xk

does there exist a sequence of integers i1,i2,....,ir.

such that

w1 wi1 wi2 .... wir=x1 xi1 xi2 ..... xir ?

Difference between PCP and MPCP is that in the MPCP, a solution is required to start with the first string on each list.