Editing Post correspondence problem (section)

== Variants ==

Many variants of PCP have been considered. One reason is that, when one tries to prove undecidability of some new problem by reducing from PCP, it often happens that the first reduction one finds is not from PCP itself but from an apparently weaker version.

* The problem may be phrased in terms of [[monoid morphism]]s ''f'', ''g'' from the free monoid ''B''<sup>&lowast;</sup> to the free monoid ''A''<sup>&lowast;</sup> where ''B'' is of size ''n''.  The problem is to determine whether there is a word ''w'' in ''B''<sup>+</sup> such that ''f''(''w'') = ''g''(''w'').<ref>{{cite book | first=Arto | last=Salomaa | author-link=Arto Salomaa | title=Jewels of Formal Language Theory | publisher=Pitman Publishing | isbn=0-273-08522-0 | year=1981 | zbl=0487.68064 | pages=74–75 }}</ref>
* The condition that the alphabet <math>A</math> have at least two symbols is required since the problem is decidable if <math>A</math> has only one symbol.
* A simple variant is to fix ''n'', the number of tiles. This problem is decidable if ''n'' ≤ 2,<ref name="EKR82">{{cite journal |last1=Ehrenfeucht|first1=A.|author-link1=Andrzej Ehrenfeucht|last2=Karhumäki|first2=J.|author-link2=Juhani Karhumäki|last3=Rozenberg |first3=G.|author-link3=Grzegorz Rozenberg |title=The (generalized) post correspondence problem with lists consisting of two words is decidable |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |date=November 1982 |volume=21 |issue=2 |pages=119–144 |doi=10.1016/0304-3975(89)90080-7 |url=https://dx.doi.org/10.1016%2F0304-3975%2889%2990080-7}}</ref> but remains undecidable for ''n'' ≥ 5. It is unknown whether the problem is decidable for 3 ≤ ''n'' ≤ 4.<ref name="N15">{{cite conference|author = T. Neary|year=2015|title=Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words|conference=STACS 2015|book-title=32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)|editor=Ernst W. Mayr and Nicolas Ollinger|publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik|volume=30|pages=649–661|doi=10.4230/LIPIcs.STACS.2015.649|doi-access=free |url=http://drops.dagstuhl.de/opus/volltexte/2015/4948/}}</ref>
* The '''''circular'' Post correspondence problem''' asks whether indexes <math>i_1, i_2,\ldots</math> can be found such that <math>\alpha_{i_1} \cdots \alpha_{i_k}</math> and <math>\beta_{i_1} \cdots \beta_{i_k}</math> are [[conjugacy|conjugate words]], i.e., they are equal modulo rotation. This variant is undecidable.<ref name="Ruohonen83">{{cite journal|author= K. Ruohonen |year =1983|title=On some variants of Post's correspondence problem|publisher=Springer|volume=19|issue=4|pages=357&ndash;367|journal=[[Acta Informatica]] | doi = 10.1007/BF00290732|s2cid =20637902}}</ref>
* One of the most important variants of PCP is the '''''bounded'' Post correspondence problem''', which asks if we can find a match using no more than ''k'' tiles, including repeated tiles. A brute force search solves the problem in time O(2<sup>''k''</sup>), but this may be difficult to improve upon, since the problem is [[NP-complete]].<ref name="GJ79">{{cite book | author = Michael R. Garey | author-link = Michael R. Garey | author2 = David S. Johnson | author2-link = David S. Johnson | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5 | page = [https://archive.org/details/computersintract0000gare/page/228 228] }}</ref> Unlike some NP-complete problems like the [[boolean satisfiability problem]], a small variation of the bounded problem was also shown to be complete for RNP, which means that it remains hard even if the inputs are chosen at random (it is hard on average over uniformly distributed inputs).<ref name="Gurevich91">{{cite journal|author = Y. Gurevich|author-link=Yuri Gurevich|journal = [[J. Comput. Syst. Sci.]]|year = 1991|pages = 346–398|volume=42|title= Average case completeness|publisher=Elsevier Science|doi = 10.1016/0022-0000(91)90007-R|issue=3|hdl=2027.42/29307|url = https://deepblue.lib.umich.edu/bitstream/2027.42/29307/1/0000370.pdf}}</ref>
* Another variant of PCP is called the '''''marked'' Post Correspondence Problem''', in which each <math>\alpha_i</math> must begin with a different symbol, and each <math>\beta_i</math> must also begin with a different symbol. Halava, Hirvensalo, and de Wolf showed that this variation is decidable in [[EXPTIME|exponential time]]. Moreover, they showed that if this requirement is slightly loosened so that only one of the first two characters need to differ (the so-called 2-marked Post Correspondence Problem), the problem becomes undecidable again.<ref name="HHW01">{{cite journal|author = V. Halava |author2=M. Hirvensalo |author3=R. de Wolf|year=2001|title=Marked PCP is decidable|journal=Theor. Comput. Sci.|publisher=Elsevier Science|volume=255|issue=1–2 |pages=193–204|doi=10.1016/S0304-3975(99)00163-2}}</ref>
* The '''Post Embedding Problem''' is another variant where one looks for indexes <math>i_1, i_2, \ldots</math> such that <math>\alpha_{i_1} \cdots \alpha_{i_k}</math> is a [[substring|(scattered) subword]] of <math>\beta_{i_1} \cdots \beta_{i_k}</math>. This variant is easily decidable since, when some solutions exist, in particular  a length-one solution exists. More interesting is the '''''Regular'' Post Embedding Problem''', a further variant where one looks for solutions  that belong to a given [[regular language]] (submitted, e.g., under the form of a regular expression on the set <math>\{1,\ldots,N\}</math>). The Regular Post Embedding Problem is still decidable but,  because of the added regular constraint, it has a very high complexity that dominates every multiply recursive function.<ref name="CS07">{{cite book|author = P. Chambart|author2=Ph. Schnoebelen|title = Post embedding problem is not primitive recursive, with applications to channel systems|year = 2007|volume =4855|pages=265–276|publisher=Springer|doi=10.1007/978-3-540-77050-3_22|series = Lecture Notes in Computer Science|isbn = 978-3-540-77049-7|url=http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/CS-fsttcs07.pdf}}</ref>
* The '''Identity Correspondence Problem''' (ICP) asks whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. The problem is undecidable and equivalent to the following Group Problem:  is the semigroup generated by a finite set of pairs of words (over a group alphabet) a group.<ref name="BP10">{{cite journal|author = Paul C. Bell |author2=Igor Potapov |title =On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups |year = 2010|journal = International Journal of Foundations of Computer Science |volume =21 |issue=6 |pages=963–978
|publisher=World Scientific |doi=10.1142/S0129054110007660
|arxiv=0902.1975}}</ref>