Solving and creating difficult instances of Post's correspondence problem.

摘要

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.