3
$\begingroup$

I'm only just starting to learn about the PCP, and I'm especially interested in the Bounded version. From Wikipedia:

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.

I am not sure I understand what Wiki means by a 'tile' in this context.

I do understand that a typical PCP problem takes as input two equal-length lists of nonempty strings, each of which contains some number of words. An example is this:

M = (abb, aa, aaa) and N = (bba, aaa, aa)

In terms of the Bounded PCP, what would the integer K be here? Is it the length an individual word can be (which in this case is maxed at 3)? Is it the length of a single list?

Hope this is clear. I appreciate any help profusely in advance.

$\endgroup$
  • $\begingroup$ You've flipped around the problem. You've given as input a pair of lists, but it takes as input a list of pairs. $\endgroup$ – jmite Nov 14 '16 at 4:47
4
$\begingroup$

Suppose your list is M=(bba,ab,bba,a) N=(bb,aa,bb,baa) Then its equivalent tile representation is as follows

enter image description here

Now your pcp problem is equivalent to finding a sequence of tiles(repetition allowed) such that concatenating all upper halves and concatenating all lower halves gives you same string. K here is nothing but number of tiles that can be used

Edit : As Yuval Filmus subtly mentions in his comment, there are many other interpretations of K. In an another formulation K can also be the maximum length of concatenated string, in which case the bounded PCP problem is Pspace complete. But usually many books refer to K as being number of tiles that are allowed.Please refer to Sipser book for more.

$\endgroup$
  • $\begingroup$ There might be several different definitions of bounded, see for example this answer. In particular, the Wikipedia definition seems to be different. $\endgroup$ – Yuval Filmus Nov 14 '16 at 8:12
  • $\begingroup$ I would say something like "finding a multiset of tiles" instead, to stress you can repeat the same tile. If you can't then the problem becomes decidable. $\endgroup$ – chi Nov 14 '16 at 8:50
  • $\begingroup$ sequence would be much better representation to insist on the order . Anyways thanks for pointing out :) $\endgroup$ – MysticForce Nov 14 '16 at 9:29
  • $\begingroup$ Thank you for the answer. For this version of the Bounded PCP, the question is whether we can find a matching solution using no more than k tiles, as opposed to the general PCP which allows an infinite supply of such tiles, right? $\endgroup$ – Fiery Phoenix Nov 14 '16 at 15:19
  • $\begingroup$ @Fiery Phoenix Yes thats true $\endgroup$ – MysticForce Nov 15 '16 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.