Problem Detail: The PARTITION problem is NP-complete: INSTANCE: finite set $A$ and a size $s(a) in mathbb{Z}^+$ for each $a in A$
QUESTION: Is there a subset $A’ subseteq A$ such that $sum_{a in A’} s(a) = sum_{a in A setminus A’} s(a)$ The problem remains NP-complete even if the elements are ordered as $a_1,a_2,…,a_{2n}$ and we require that $A’$ contains exactly one of $a_{2i-1},a_{2i}$ for $1 leq i leq n$ (Garey and Johnson, Computers and Intractability). This variant should be known as EVEN-ODD PARTITION. Do you see a quick reduction to prove its hardness? (or do you know the paper where it was first defined and proved)
QUESTION: Is there a subset $A’ subseteq A$ such that $sum_{a in A’} s(a) = sum_{a in A setminus A’} s(a)$ The problem remains NP-complete even if the elements are ordered as $a_1,a_2,…,a_{2n}$ and we require that $A’$ contains exactly one of $a_{2i-1},a_{2i}$ for $1 leq i leq n$ (Garey and Johnson, Computers and Intractability). This variant should be known as EVEN-ODD PARTITION. Do you see a quick reduction to prove its hardness? (or do you know the paper where it was first defined and proved)
Asked By : Vor
Answered By : Karolis Juodelė
Let $b_i = a_{2i} – a_{2i-1}$. The problem is then finding $sum varepsilon_i b_i = 0$. Here $varepsilon_i = 1$ if $a_{2i} in A’$ and $-1$ otherwise. Let $B’ = {b_i mid varepsilon_i = 1}$. Note that $sum_{b in B’} b = sum _{b in B setminus B’} b$. Thus solving PARTITION of $B$ would solve EVEN-ODD PARTITION of $A$. Let $b_{2i} = a_i$ and $b_{2i-1} = 0$. Note that if $b_{2i} in B’ leftrightarrow a_i in A’$ and $sum_{B’} = sum_{B setminus B’}$ then $sum_{A’} = sum_{A setminus A’}$. Thus solving EVEN-ODD PARTITION on $B$ would solve PARTITION on $A$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19271 Ask a Question Download Related Notes/Documents
