<p>The problem is NP-hard already for <span class="math-container">$\Sigma = \{a, b\}$</span>. (Of course, it is in PTIME if <span class="math-container">$|\Sigma| = 1$</span>.) The reduction is from <em><a href="https://en.wikipedia.org/wiki/3-partition_problem" rel="noreferrer">distinct-input 3-partition</a></em> 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 <span class="math-container">$S$</span> of <span class="math-container">$3m$</span> positive integers having sum <span class="math-container">$mT$</span>, we must determine if we can partition <span class="math-container">$S$</span> into triples that all have sum <span class="math-container">$T$</span>. The numbers are assumed to be strictly between <span class="math-container">$T/4$</span> and <span class="math-container">$T/2$</span>: this ensures that the sum of strictly less than 3 numbers is always <span class="math-container">$&lt;T$</span> and the sum of strictly more than 3 numbers is always <span class="math-container">$&gt;T$</span>.</p>
<p>The input strings are then the following (all distinct):</p>
<ul>
<li><span class="math-container">$3m$</span> strings <span class="math-container">$a^i$</span> for each <span class="math-container">$i \in S$</span></li>
<li><span class="math-container">$m$</span> strings <span class="math-container">$b^i$</span> for <span class="math-container">$1 \leq i \leq m$</span></li>
</ul>
<p>The target string is: <span class="math-container">$\bigodot_{1 \leq i \leq m} a^T b^i$</span>.</p>
<p>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 <span class="math-container">$m$</span> other strings in the correct order. Conversely, given a solution to the problem, we know that the  <span class="math-container">$m$</span> blocks <span class="math-container">$b^i$</span> can only be achieved by the <span class="math-container">$m$</span> strings of the second kind, the only way to achieve <span class="math-container">$m$</span> blocks is to use them in the order <span class="math-container">$b^1, \ldots, b^m$</span>. 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 <span class="math-container">$T/4$</span> and <span class="math-container">$T/2$</span> ensures that we have 3 strings per class in the partition, and they sum to <span class="math-container">$T$</span>, giving a solution to the 3-partition problem.</p>

CC BY-SA 4.0
2023-03-11T11:15:41.927Z
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?
leftaroundabout
CC BY-SA 4.0
2023-03-11T15:54:28.163Z
@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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-03-10T22:31:30.650Z
2023-03-10T22:31:30.650Z
Antoine Amarilli 'a3nm'
<p>Consider the following decision problem over a fixed alphabet <span class="math-container">$\Sigma$</span>:</p>
<ul>
<li>Input: strings <span class="math-container">$s_1, \ldots, s_n$</span> of <span class="math-container">$\Sigma^*$</span> and a target string <span class="math-container">$t \in \Sigma^*$</span></li>
<li>Output: does there exist a permutation <span class="math-container">$\sigma\colon \{1, \ldots, n\} \to \{1, \ldots n\}$</span> such that the concatenation <span class="math-container">$s_{\sigma(1)} \cdots s_{\sigma(n)}$</span> is equal to <span class="math-container">$t$</span></li>
</ul>
<p>This problem is clearly in NP. Is it NP-hard? I didn't find a reference to it in Garey &amp; Johnson or on the Internet. It is related to the <a href="https://en.wikipedia.org/wiki/Post_correspondence_problem" rel="nofollow noreferrer">bounded version of the Post correspondence problem</a>, which is NP-hard, but there the number of times we use each string isn't prescribed.</p>

<np-hardness><permutations><scheduling>
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
Antoine Amarilli 'a3nm'
# Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

(Asked by: username_0 on 2023-03-10)

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](https://en.wikipedia.org/wiki/Post_correspondence_problem), which is NP-hard, but there the number of times we use each string isn't prescribed.

**Tags:** np-hardness, permutations, scheduling

---

## 1 answers

### Answer by username_0 on 2023-03-10. Score: 9 | Accepted answer

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](https://en.wikipedia.org/wiki/3-partition_problem)* 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 $ 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.

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  

---

