Post’s correspondences problem(波斯特對應問題，縮寫為PCP)的難易程度以往是由各集合中解答的長度所決定，解答的長度越長者難度越高，然而這並無法公平客觀的面對所有instances。故本論文提出一套有別於以往的困難度定義：即解題時間除以該例子所得到有解的數目。
本篇論文有兩個主要方向：其一是使用較小size與width的instance透過「PCP基因重整繁衍」之演算法，繁衍出特定不同的size與width的instances，並使用由「Solver」程式改寫而成的「Hard index solver」程式做為困難度判定的指標，重覆地篩檢，進而產生特定不同的size與width且合法有解的instance，以做為後續實驗的素材，並供後人研究參考。其二則是藉由前人所定義的困難度指標所留下較困難的200 hard instances，與本論文透過「PCP基因重整繁衍」之演算法並藉由新定義的困難度指標所找出較困難的200 hard instances做一比較，以證明本論文所定義的困難度有其較合理的意義。

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.

[1] A. Ehrenfeucht, J. Karhumaki and G. Rozenberg, “The (generalized) Post correspondence problem with lists consisting of two words is decidable,” Theoretical Computing Science, pp.119-144, Vo1. 21,No. 2, 1982.
[2] M. R. Garey, and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
[3] V. Halava, T. Harju and M. Hirvensalo, “Binary (generalized) Post correspondence problem,” TUCS Technical Report, No. 357, August 2000.
[4] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory and Computation, Addison-Wesley, 1979.
[5] R. J. Lorentz, “Creating difficult instances of the Post correspondence problem,” The Second International Conference on Computers and Games (CG’2000), Hamamatsu, Japan, pp.145-159, 2000.
[6] Y. Matiyasevich and G. Senizergues, “Decision problems for semi-Thue systems with a few rules,” 11th Annual IEEE Symposium on Logic in Computer Science, 1996.
[7] M. Schmidt, H. Stamer and J. Waldmann, “Busy beaver PCPs,” Fifth International Workshop on Termination (WST ’01), Utrecht, The Netherlands, 2001.
[8] H. Stamer, “PCP At Home, ”
http://flower.theory.informatik.uni-kassel.de/~stamer/pcp/pcpcontest_en.html.
[9] L. Zhao, “PCP A nice problem, ” In http://www.cs.ualberta.ca/~zhao/PCP/.
[10] L. Zhao, Solving and creating difficult instances of Post’s correspondence problem, MSc thesis, Department of Computing Science, University of Alberta, 2002.
[11] 李維 (民國86年3月)， 精通Borland C++ Builder – 視覺化 C/C++程式設計<基礎篇>， 博碩顧問股份有限公司。
[12] 林育匡(民96)， 現今最少提示數之數獨盤面產生器研究，國立台灣師範大學資訊工程研究所碩士論文。
[13] 施威銘研究室， (民國93年05月)， 最新Java 2程式語言， 旗標出版股份有限公司。
[14] 蔡明志 (民國93年08月)， 資料結構使用JAVA ，碁峯資訊股份有限公司。