10
$\begingroup$

Consider the following decision problem over a fixed alphabet $\Sigma$:

  • Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$
  • Output: does there exist a permutation $\sigma\colon \{1, \ldots, n\} \to \{1, \ldots n\}$ such that the concatenation $s_{\sigma(1)} \cdots s_{\sigma(n)}$ is equal to $t$

This problem is clearly in NP. Is it NP-hard? I didn't find a reference to it in Garey & Johnson or on the Internet. It is related to the bounded version of the Post correspondence problem, which is NP-hard, but there the number of times we use each string isn't prescribed.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
8
$\begingroup$

The problem is NP-hard already for $\Sigma = \{a, b\}$. (Of course, it is in PTIME if $|\Sigma| = 1$.) The reduction is from distinct-input 3-partition which is strongly NP-hard, i.e., intractable also if the input is given in unary, as is the case here. Given as input a set $S$ of $3m$ positive integers having sum $mT$, we must determine if we can partition $S$ into triples that all have sum $T$. The numbers are assumed to be strictly between $T/4$ and $T/2$: this ensures that the sum of strictly less than 3 numbers is always $<T$ and the sum of strictly more than 3 numbers is always $>T$.

The input strings are then the following (all distinct):

  • $3m$ strings $a^i$ for each $i \in S$
  • $m$ strings $b^i$ for $1 \leq i \leq m$

The target string is: $\bigodot_{1 \leq i \leq m} a^T b^i$.

If there is a solution to the unary 3-partition instance then we obtain a solution to the problem by concatenating the strings to form the triples of the solution, separated by the $m$ other strings in the correct order. Conversely, given a solution to the problem, we know that the $m$ blocks $b^i$ can only be achieved by the $m$ strings of the second kind, the only way to achieve $m$ blocks is to use them in the order $b^1, \ldots, b^m$. We can partition the strings of the first kind based on where they occur between these factors. The fact that the integers are strictly between $T/4$ and $T/2$ ensures that we have 3 strings per class in the partition, and they sum to $T$, giving a solution to the 3-partition problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Correct, but oh my is this ugly. The input strings are all completely degenerate. Clearly there are heuristics that work in polynomial time for typical strings; can we come up with a good condition on the strings that ensures PTIME? I don't suppose a fixed bound on the length of constant runs of the same symbol would be enough? $\endgroup$
    – leftaroundabout
    Mar 11 at 11:15
  • 2
    $\begingroup$ @leftaroundabout: Your proposed bound would not work, it suffices to replace $a$ and $b$ in my reduction, e.g., by repeated factors $ab$ and $ba$. More generally my question was to know the worst-case complexity, not the "typical" complexity; though it is always interesting to know if there are tractable subcases. One thing that clearly works is to allow multisets but assume that the length of strings is bounded by a constant, so there are only constantly many possible input strings in the multiset and dynamic programming works. $\endgroup$
    – a3nm
    Mar 11 at 15:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.