<p>Bounded Post Correspondence Problem is defined as follows:
given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{i_1} \ldots x_{i_k} = y_{i_1} \ldots y_{i_k}$. It is obviously NP-complete.</p>

<p>Consider another constraint: the indexes has to be unique, which each pair may appear at most once in the concatenation. 
I have constructed simple reduction from 3-PARTITION. The 3-PARTITION instance is given by number $B$ and list $A=(a_1, \ldots ,a_{3m})$ of $3m$ integers. The problem is to find 3-element disjoint subsets $S_1, \ldots, S_m$ such, that the sum of the numbers in each subset is equal $B$.</p>

<p>The reduction to 3-PARTITION is to construct following pairs:</p>

<ol>
<li>$(0,0\{\#^{B}1\}^{m} )$</li>
<li>$m$ pairs of form: $(1,2)$</li>
<li>$( \# ^{a_i},* ) $ for each $a_{i} \in  A$</li>
<li>$(\{ *** 2\}^{m} 0,0)$</li>
</ol>

<p>So the numbers from A are coded in unary form. We may do so, since 3-PARTITION is NP-complete in the strong sense.</p>

<p>It is supposed to work as follows: first the (1) block is used. Then for some subset $S_l=(a_i,a_j,a_k)$ the corresponding (3) blocks are added and the separator block (2) next. After all subsets are used, the ending (4) block has to be added.</p>

<p>Suppose now, that the index sequence is found. Using it we can construct solution of the 3-PARTITION since the pairs corresponding to element of A must form 3-element groups and all of them must be used to 'fill' the (1) block.</p>

<p>Is there any simple connection between the standard and the modified PCP?
Is there any simple reduction from the modified to the standard problem?
Can we say that the modified version is in some sense a special case of the standard problem?</p>

CC BY-SA 3.0
2011-05-13T15:52:23.787Z
Why is your Bounded Post Correspondence Problem NP-complete? If the input $K$ is too large then the length of possible sequences is exponential in your input length.
Marc Bury
CC BY-SA 3.0
2011-05-13T15:58:53.107Z
@Marc The definition of this variant is taken from wikipedia, See: http://en.wikipedia.org/wiki/Post_correspondence_problem#cite_ref-GJ79_3-0
anacrusis
CC BY-SA 3.0
2011-05-14T00:46:12.477Z
Okay, in the definition in the Garey-Johnson book it is $K \leq n$ :-)
Marc Bury
CC BY-SA 3.0
2016-11-29T09:26:05.933Z
Does anybody know if the BPCP ist strong or weak NPC?
user43436
<cc.complexity-theory><np-hardness><partition-problem><post-correspondence>
Post Correspondence Problem "binary" variant
anacrusis
# Post Correspondence Problem "binary" variant

(Asked by: username_0 on 2011-05-12)

Bounded Post Correspondence Problem is defined as follows:
given list of pairs of words $ (x\_1,y\_1), \ldots, (x\_n, y\_n) $ and $K$ find sequence of indexes $i\_1, \ldots, i\_k$, $k \leq K$ so that $x\_{i\_1} \ldots x\_{i\_k} = y\_{i\_1} \ldots y\_{i\_k}$. It is obviously NP-complete.

Consider another constraint: the indexes has to be unique, which each pair may appear at most once in the concatenation.
I have constructed simple reduction from 3-PARTITION. The 3-PARTITION instance is given by number $B$ and list $A=(a\_1, \ldots ,a\_{3m})$ of $3m$ integers. The problem is to find 3-element disjoint subsets $S\_1, \ldots, S\_m$ such, that the sum of the numbers in each subset is equal $B$.

The reduction to 3-PARTITION is to construct following pairs:

1. $(0,0\{\#^{B}1\}^{m} )$
2. $m$ pairs of form: $(1,2)$
3. $( \# ^{a\_i},\* ) $ for each $a\_{i} \in A$
4. $(\{ \*\*\* 2\}^{m} 0,0)$

So the numbers from A are coded in unary form. We may do so, since 3-PARTITION is NP-complete in the strong sense.

It is supposed to work as follows: first the (1) block is used. Then for some subset $S\_l=(a\_i,a\_j,a\_k)$ the corresponding (3) blocks are added and the separator block (2) next. After all subsets are used, the ending (4) block has to be added.

Suppose now, that the index sequence is found. Using it we can construct solution of the 3-PARTITION since the pairs corresponding to element of A must form 3-element groups and all of them must be used to 'fill' the (1) block.

Is there any simple connection between the standard and the modified PCP?
Is there any simple reduction from the modified to the standard problem?
Can we say that the modified version is in some sense a special case of the standard problem?

**Tags:** cc.complexity-theory, np-hardness, partition-problem, post-correspondence

> **Comments:**
> **username_1**: Why is your Bounded Post Correspondence Problem NP-complete? If the input $K$ is too large then the length of possible sequences is exponential in your input length.  
> **username_0**: @Marc The definition of this variant is taken from wikipedia, See: http://en.wikipedia.org/wiki/Post_correspondence_problem#cite_ref-GJ79_3-0  
> **username_1**: Okay, in the definition in the Garey-Johnson book it is $K \leq n$ :-)  
> **username_2**: Does anybody know if the BPCP ist strong or weak NPC?  

---

## 0 answers

