Registered: Aug 2003
Posts: 712

Emile Post's classic correspondance problem asks whether ordered pairs (or longer sets) of strings can be concatenated to yield the same string, a problem of satisfying a simple constraint. For a trivial example, if you have x1 = {ABB, A} and x2 = {A, BBA} you can take x1x2 and get {ABBA, ABBA}.

The question for any initial set of strings it whether you can bring the sequences into "correspondance" (equal strings on removal of parenthesis) by putting together any of the set you have, in any order. You can vary the number of allowed symbols, the number of parallel strings to match up, and the maximum length of the initial strings, as parameters of the problem.

The NKS book discusses these as "correspondance systems", in the main text on pages 757 and thereabouts, and at length in one of the notes on page 1139.

A graduate student in Alberta has a nice site about the PCP problem that I thought might be of interest to forum members, here -

http://www.cs.ualberta.ca/~zhao/PCP/intro.htm

I hope this is interesting.

Report this post to a moderator | IP: Logged