The PARTITION decision problem is defined as follows (taken from COMPUTERS AND INTRACTABILITY from Garey and Johnson):

Instance: A 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). $$

This problem is NP-complete via standard reductions. I need to know whether PARTITION is NP-complete via first order reductions, more specifically via first order projections. If you know the answer, and the answer is positive, please point to the source of the proof.

The proofs of hardness (in the standard setting) I've seen take an NP-complete problem, such as SUBSET SUM, and transform every instance of it into an equivalent instance of PARTITION with at least one size $s(a)$ being the sum of other sizes. It seems to me these proofs can't have descriptive counterparts because of the sum involved (to my knowledge it is not first order definable).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.