Motivated by 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.