patternMinor
What is 'K' in the Bounded Post Correspondence Problem?
Viewed 0 times
problemthewhatpostcorrespondencebounded
Problem
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:
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.
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.
Solution
Suppose your list is M=(bba,ab,bba,a) N=(bb,aa,bb,baa) Then its equivalent tile representation is as follows
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.
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.
Context
StackExchange Computer Science Q#66023, answer score: 4
Revisions (0)
No revisions yet.