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

Your Answer

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

Browse other questions tagged or ask your own question.