Research on the Generator of Hard Instances

[[abstract]]The hardness of an instance of the Post’s correspondences problem (abbreviated to PCP) was defined in the past based on its solutions’ lengths. That is, the longer the lengths of the solutions are, the harder the instance becomes. But this cannot reflect the real characteristic of the hard instances. In this thesis, we present a new definition of the hardness for the PCP where the solving time divided by the number of solutions is defined as the index of the hardness of a PCP instance. This thesis is composed of two major parts. Firstly, starting from the PCP instances with smaller sizes and widths, we use a "PCP genes restructuring" algorithm to generate lots of PCP instances with larger sizes and widths. To filter those PCP instances, we rewrite the "Solver" program to be "Hard index solver". At last, some of the legal and solvable instances are remained and kept into our PCP database, which can be used in the future research. Secondly, we compare the 200 hard instances derived by previous researchers with the 200 harder instances derived from our study. Through this comparison, we are able to show that our new definition for the hardness of the PCP instance is more reasonable than previous definition.