Post’s Correspondence Problem之困難例子

Research on the Generator of Hard Instances

江陳威(CHIANG CHEN-WEI)

指導教授 ： 林順喜

國立臺灣師範大學/教育學院/資訊教育學系/碩士(2007年)

摘要

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.

並列關鍵字

Post’s correspondences problem ； undecidable problem ； genes restructuring algorithm ； genetic algorithm

參考文獻

[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.