Tag Info

This problem, that I will call Subset-Perm-Sum, is NP-complete. Membership is easy: guess the subset non-deterministically and then check. For hardness one can reduce from 3CNF-SAT in a very similar way to the standard proof of hardness for Subset-Sum. Let $\varphi$ be an input formula with $v$ variables and $c$ clauses. We will build an instance of Subset-...