<p>It is possible to reduce from the "unshuffling a string" problem: given a string $w \in \Sigma^*$, decide whether $w$ is a shuffle square, i.e. $w$ is in the shuffle product of two identical strings. This problem is proved to be NP-complete for alphabet of size at least nine, see <a href="https://cstheory.stackexchange.com/questions/34/how-hard-is-unshuffling-a-string">this question</a> for references and discussion. </p>

<p>Here, for two strings $u$ and $v$  the shuffle product is defined as the set of all $w = u_1 v_1 \ldots u_i v_i$ for each representation $u = u_1 \ldots u_k$ and $v = v_1 \ldots v_k$ with $u_i, v_i \in \Sigma^*$ (i.e. $u_i$ and $v_i$ are strings, not letters).</p>

<p>The reduction is easy: given $w = a_1 \ldots a_n$, $a_i \in \Sigma$, take $x_{i, 0} = a_i$ and $x_{i, 1} = \epsilon$, where $\epsilon$ is the empty string. Then the answer in your problem (with alphabet of size nine) is YES if and only if $w$ is a shuffle square.</p>

<p>Finally, use an arbitrary prefix-free binary encoding of $\Sigma$, thus getting a reduction for the binary case.</p>

CC BY-SA 3.0
2017-09-05T07:25:18.833Z
Also the case in which we don't allow the $\epsilon$ seems interesting (the strings are from $\{0,1\}^+$) ... I don't see a quick fix for the reduction for this case.
Marzio De Biasi
CC BY-SA 3.0
2017-09-07T12:53:36.080Z
While the wording of the problem allows empty strings, the interesting cases (as pointed out by Marzio) occur when both $x_{i, 0}$ and $x_{i, 1}$ are not equal to $\epsilon$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-09-03T19:41:14.190Z
2017-09-03T21:57:04.510Z
2017-09-03T21:57:04.510Z
Andrew Ryzhikov
<p>Motivated by <a href="https://cs.stackexchange.com/questions/19271/hardness-proof-of-even-odd-partition">Hardness proof of EVEN-ODD PARTITION</a> post I came up with a string version.</p>

<p><strong>String even-odd partition</strong></p>

<p><strong>INPUT:</strong> $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e.,  $n$ pairs of strings over $\{0,1\}^*$ </p>

<p><strong>QUESTION:</strong> Does there exist $(b_1,\dots,b_n) \in \{0,1\}^n$ such that $x_{1,b_1} \cdots x_{n,b_n} = x_{1,1-b_1} \cdots x_{n,1-b_n}$?</p>

<p>Equivalently: for each pair, we can either swap the two strings or leave them alone; then we want to know if the concatenation of the left part of each pair can equal the concatenation of the right part of each pair.</p>

<p>Or, in other words, we are trying to partition every pair into two strings to obtain concatenated strings $W_{even} $ and $W_{odd}$  such that $W_{even}= W_{odd}$, where exactly one string from each pair goes to $W_{even}$  and the other goes to $W_{odd}$.  The selected strings have to stay in the same order they appear in the input.</p>

<p>It feels like this should be NP-complete by a reduction from even-partition problem but I can't find an explicit reduction; I am having difficulty in representing integers by appropriate strings.</p>

<blockquote>
  <p>Is there a simple reduction to prove the NP-completeness of this string variant?</p>
</blockquote>

<p>This was posted first on <a href="https://cs.stackexchange.com/questions/70668/string-version-of-even-odd-partition-problem">CS StackExchange</a>.</p>

CC BY-SA 3.0
2017-06-11T18:36:22.623Z
How about unary?
KWillets
CC BY-SA 3.0
2017-06-14T07:12:56.837Z
@KWillets If the strings are in unary, then a simple dynamic programming approach works in polynomial time.
Mikhail Rudoy
CC BY-SA 3.0
2017-06-26T18:03:26.350Z
Do you know the answer for "classic" partition where you simply have a string set $S$ and you want a partition $S_1,S_2$ and an order on $S_1$ and $S_2$ such that the concatenation of $S_1$ equals the concatenation of $S_2$?

It might be easier to reduce to this, and if the "classic" problem is not hard, neither is yours.
R B
CC BY-SA 3.0
2017-06-29T05:24:13.227Z
@RB No. Your version of partition appears to be hard.
Mohammad Al-Turkistany
<cc.complexity-theory><np-hardness>
String version of even-odd partition problem
Mohammad Al-Turkistany
# String version of even-odd partition problem

(Asked by: username_0 on 2017-06-10)

Motivated by [Hardness proof of EVEN-ODD PARTITION](https://cs.stackexchange.com/questions/19271/hardness-proof-of-even-odd-partition) post I came up with a string version.

**String even-odd partition**

**INPUT:** $(x\_{1,0},x\_{1,1}),\dots,(x\_{n,0},x\_{n,1})$, i.e., $n$ pairs of strings over $\{0,1\}^\*$

**QUESTION:** Does there exist $(b\_1,\dots,b\_n) \in \{0,1\}^n$ such that $x\_{1,b\_1} \cdots x\_{n,b\_n} = x\_{1,1-b\_1} \cdots x\_{n,1-b\_n}$?

Equivalently: for each pair, we can either swap the two strings or leave them alone; then we want to know if the concatenation of the left part of each pair can equal the concatenation of the right part of each pair.

Or, in other words, we are trying to partition every pair into two strings to obtain concatenated strings $W\_{even} $ and $W\_{odd}$ such that $W\_{even}= W\_{odd}$, where exactly one string from each pair goes to $W\_{even}$ and the other goes to $W\_{odd}$. The selected strings have to stay in the same order they appear in the input.

It feels like this should be NP-complete by a reduction from even-partition problem but I can't find an explicit reduction; I am having difficulty in representing integers by appropriate strings.

> Is there a simple reduction to prove the NP-completeness of this string variant?

This was posted first on [CS StackExchange](https://cs.stackexchange.com/questions/70668/string-version-of-even-odd-partition-problem).

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: How about unary?  
> **username_2**: @KWillets If the strings are in unary, then a simple dynamic programming approach works in polynomial time.  
> **username_3**: Do you know the answer for "classic" partition where you simply have a string set $S$ and you want a partition $S_1,S_2$ and an order on $S_1$ and $S_2$ such that the concatenation of $S_1$ equals the concatenation of $S_2$?  It might be easier to reduce to this, and if the "classic" problem is not hard, neither is yours.  
> **username_0**: @RB No. Your version of partition appears to be hard.  

---

## 1 answers

### Answer by username_4 on 2017-09-03. Score: 3

It is possible to reduce from the "unshuffling a string" problem: given a string $w \in \Sigma^\*$, decide whether $w$ is a shuffle square, i.e. $w$ is in the shuffle product of two identical strings. This problem is proved to be NP-complete for alphabet of size at least nine, see [this question](https://cstheory.stackexchange.com/questions/34/how-hard-is-unshuffling-a-string) for references and discussion.

Here, for two strings $u$ and $v$ the shuffle product is defined as the set of all $w = u\_1 v\_1 \ldots u\_i v\_i$ for each representation $u = u\_1 \ldots u\_k$ and $v = v\_1 \ldots v\_k$ with $u\_i, v\_i \in \Sigma^\*$ (i.e. $u\_i$ and $v\_i$ are strings, not letters).

The reduction is easy: given $w = a\_1 \ldots a\_n$, $a\_i \in \Sigma$, take $x\_{i, 0} = a\_i$ and $x\_{i, 1} = \epsilon$, where $\epsilon$ is the empty string. Then the answer in your problem (with alphabet of size nine) is YES if and only if $w$ is a shuffle square.

Finally, use an arbitrary prefix-free binary encoding of $\Sigma$, thus getting a reduction for the binary case.

> **Comments:**
> **username_5**: Also the case in which we don't allow the $\epsilon$ seems interesting (the strings are from $\{0,1\}^+$) ... I don't see a quick fix for the reduction for this case.  
> **username_0**: While the wording of the problem allows empty strings, the interesting cases (as pointed out by Marzio) occur when both $x_{i, 0}$ and $x_{i, 1}$ are not equal to $\epsilon$.  

---

