Master thesis

Author:
    Ling Zhao (zhao at cs.ualberta.ca)
    Department of Computing Science
    University of Alberta

Supervisors:
    Dr. Jonathan Schaeffer
    Dr. Martin Mueller

Title:
    Solving and Creating Difficult Instances of Post's 
    Correspondence Problem

Abstract:

Post's correspondence problem (PCP) was invented by Emil L. Post
in 1946. It is an undecidable problem, which means that it is
impossible to find an algorithm to solve the whole problem. This
problem has been extensively discussed in the theoretical computer
science literature, but only recently did some researchers begin to
look into the empirical properties of this problem.

Although this problem cannot be completely solved, some of its
instances can be solved and may have very long solutions. It is
instructive and important to find instances that have very long
shortest solutions to reveal new properties and understand the 
complexity of this problem.

In this thesis, several problem-specific search enhancements have
been employed to find the shortest solutions of instances
efficiently and effectively. New disproof methods were invented to
identify instances that have no solution. All of these methods made
it possible to completely solve 7 PCP subclasses and to fully scan
3 other PCP subclasses. Our effort culminated in the discovery
of 199 hard instances with very long shortest solutions and in 
setting new records for the hardest instances known in 4 PCP 
subclasses. In addition, we present experimental results on several 
important properties of PCP and on the search and disproof methods 
used. These results will lead to a better understanding of the
theoretical and empirical properties of this problem.