5
$\begingroup$

Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of indices.

Is this a known problem? Is it NP-complete?

Details:

  1. The words $w_1,\dots,w_n$ are part of the input. Therefore, there is no a priori upper bound on $n$, $|w_i|$, or $|w|$. However, we may assume that $|w|=\sum |w_i|$.

  2. If we restrict the problem to instances with $|w_i|\le k$ (where $k$ is a fixed constant), we obtain a new problem $WT_k$. $WT_k$ belongs to $P$. It's possible to build a polynomial-time algorithm for $WT_k$, using dynamic programming. Indeed, in this case the number of different words $w_i$ is bounded by $2^k$. Hence any sequence $\{w_1,\ldots,w_n\}$ can be encoded by a $2^k$-tuple of integers (an element of $\mathbb{Z}^{2^k}$). It is convenient to assume that $w_i\ne \varepsilon$.

    Now with every initial segment $w'$ of $w$ we associate a set of tuples in $\mathbb{Z}^{2^k}$ that describe sequences of $w_i$'s resulting in $w'$. For instance, with $\varepsilon$ we associate a single tuple $(0,\ldots,0)$ and $\varepsilon$ is considered processed. Then for every processed segment $w'$ we go over its tuples and see which ones we can append to $w'$ (which $w_i$'s are still available). For instance, if $w' w_i$ gives another initial segment $w''$ of $w$ then we add the corresponding tuple for $w''$. Eventually, all initial segments will be covered. Here it is crucial that $k$ is fixed, as it ensures that the sets of tuples associated with every $w'$ is polynomially bounded (with a very large degree).

  3. I suspect that the general problem is NP-complete and I'd appreciate any suggestions.

  4. Clearly the problem can be viewed as a sort of a bounded Post correspondence problem with a fixed collection of pairs $(w,\varepsilon),(\varepsilon,w_1),\ldots,(\varepsilon,w_n)$. Not sure if this helps, though.

  5. Clearly, the restriction to a binary alphabet is irrelevant. One can work with any countable alphabet. Need to be careful though: the item 2 does not hold when the alphabet is unbounded.

$\endgroup$
  • $\begingroup$ The PCP-problem here is confusing rather than helpful. In PCP one may reuse the pairs (or even omit some). Moreover PCP is tied to undecidablity? $\endgroup$ – Hendrik Jan Oct 13 '14 at 0:21
  • $\begingroup$ Have you looked at shuffle languages? $\endgroup$ – Pseudonym Oct 13 '14 at 1:58
  • $\begingroup$ No, I know nothing about shuffle languages. The name sounds very promising. I will look into that. If you have more information, please share. $\endgroup$ – user59343 Oct 13 '14 at 13:15
  • $\begingroup$ Ok, I found this paper: users.soe.ucsc.edu/~manfred/pubs/J1.pdf which claims a very similar result "The following problem is NP-complete. Given $w,w_1,\ldots,w_n$ decide if $w$ is in the shuffle of $w_1,\ldots,w_n$". I just do not completely understand the definition of shuffle on page 347 and the real meaning of Theorem 3.1. I will try to get through the proof I guess. $\endgroup$ – user59343 Oct 13 '14 at 14:02
  • $\begingroup$ No, unfortunately, shuffle operator allows to cut through $w_i$'s. So the results by A. Mansfield, M. Warmuth, D. Haussler are not applicable in a direct way. Links: "On the computational complexity of a merge recognition problem" by A. Mansfield in Discrete Applied Mathematics and "On the complexity of iterated shuffle" by M. Warmuth, D. Haussler, in Journal of Computer and System sciences. $\endgroup$ – user59343 Oct 13 '14 at 14:38
3
$\begingroup$

I can't speak to whether it's a known problem, but it is NP-complete.

It's clearly in NP, so we just have to show NP-hardness. The following reduction is from the strongly NP-hard 3-partition problem, which asks, given a multiset of positive integers $[x_1,\ldots,x_{3m}]$, whether there exists a partition into $m$ submultisets such that the sum of each submultiset is equal to the integer $s=\frac{1}{m}\sum_{i=1}^{3m}x_i$. For each $i\in\{1,\ldots,3m\}$, make a string $a^{x_i}$. Make $m-1$ strings $b$. The target word $w$ is

$$a^sba^sb\cdots ba^s.$$

$\endgroup$
  • $\begingroup$ The 3-partition problem additionally requires that each submultiset have exactly 3 integers in it. I don't understand how your reduction enforces that. Am I missing something? $\endgroup$ – D.W. Aug 13 '18 at 22:28
  • $\begingroup$ @D.W. I should say, the 3-partition problem where all numbers are in the range (s/4, s/2), which per Wikipedia is still hard. $\endgroup$ – David Eisenstat Aug 13 '18 at 23:41
2
$\begingroup$

The problem is NP-complete. This can also be done very simply with sub-set sum:

Given a set of numbers $x_1, x_2, ... x_n$ that sums to $s$ and a number $k$. For each number $x_i$, make 2 words $a^{x_i}$ and $b^{x_i}$. The word $w$ is $a^{k}b^{k}a^{s-k}b^{s-k}$

  • If there is a subset that sums to $k$, then we can construct the word $w$ by using the corresponding $a^{x_i}$'s to build the first part of the word $w$.

    The corresponding $b^{x_i}$'s are used to build the second part of $w$. All other words are used to form the other part of $w$

  • If there is permutation that forms $w$, then we look at the first part that contains just $a$ see which words form that part. And then we take their corresponding numbers from the original subset to form the subset that sums to $k$.

The transformation is in poly-time. For the length of the transformed input, we can encode each word with just a pair of character and number to avoid too long input.

$\endgroup$
  • $\begingroup$ Unfortunately, this reduction takes exponential time. The word $w$ has length at least $k$, which is exponentially large, as the size of the input is $\lg k$. Therefore, this does not appear to be a valid proof of NP-completeness. $\endgroup$ – D.W. Aug 13 '18 at 22:29

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.