1
vote
Accepted
Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning
I think you took the problem the wrong way, but your idea is good.
Let $A = \{a_1, …, a_n\}$ be an instance of $2$-$\texttt{Partition}$. Let $B = \{(a_1 + 1, 1), …, (a_n+1, 1)\}$. Then $A$ is a ...
- 11.5k
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
reductions × 1221complexity-theory × 572
np-complete × 350
turing-machines × 229
computability × 219
np-hard × 147
undecidability × 126
np × 98
graphs × 95
algorithms × 76
satisfiability × 73
decision-problem × 63
halting-problem × 51
polynomial-time-reductions × 48
formal-languages × 43
polynomial-time × 43
proof-techniques × 38
3-sat × 35
space-complexity × 30
optimization × 27
complexity-classes × 27
time-complexity × 26
partitions × 20
semi-decidability × 19
approximation × 17