Welcome to PCP@HOME!

PCP is an abbreviation for Post's Correspondence Problem. This theoretical computer sience problem was published 1946 by Emil Post in the Bulletins of the American Math. Society -- Vol. 53. Post proved the undeciablility in the general case and introduced for the first time a concrete combinatorial puzzle, which was not recursively solvable in the Turing computational model.

The PCP is defined as follows:
Let ((p₁, q₁), (p₂, q₂), ... , (p_M, q_M)) be a finite sequence of word pairs with p₁, q₁, p₂, q₂, ..., p_M, q_M in {0,1}⁺. We say that a sequence of indices i₁, i₂, ..., i_N is a solution of length N, if p_i1 p_i2 ... p_iN = q_i1 q_i2 ... q_iN.

The general (undecidable) case can be bounded in several ways to obtain new problem classes. For example, let us consider the number of pairs M. If M = 1 or M = 2 PCP is decidable; for M >= 7 the undecidability was proven. We denote M as size of a given PCP instance. If this size 3 <= M <= 6 the decidablility is currently an open question. In our project we would examine such cases. For practical reasons we restrict the length of the words p₁, q₁, p₂, q₂, ..., p_M, q_M by an upper bound called width.

The main goal of this project is to find short PCP instances with large shortest solutions. Such cases may contain difficulties, from which we try to derive decidability criterias for restricted PCP classes.

To find such hard instances we need your help. If you would like to contribute, please read the section contest. An up-to-date list of some can be found here. If you want to solve a simple problem by hand, you should try our puzzle game.