2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Marc Bury
    May 13, 2011 at 15:52
  • $\begingroup$ @Marc The definition of this variant is taken from wikipedia, See: en.wikipedia.org/wiki/… $\endgroup$
    – anacrusis
    May 13, 2011 at 15:58
  • $\begingroup$ Okay, in the definition in the Garey-Johnson book it is $K \leq n$ :-) $\endgroup$
    – Marc Bury
    May 14, 2011 at 0:46
  • $\begingroup$ Does anybody know if the BPCP ist strong or weak NPC? $\endgroup$
    – user43436
    Nov 29, 2016 at 9:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.