# Interesting SUBSET-SUM problems

I know the following variants of SUBSETSUM problems: $\mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L}$ (Elberfeld at. al., 2010), NP-complete $\mathtt{SUBSETSUM}$, and NEXP-complete $\mathtt{SUCCINCT\mbox{-}SUBSETSUM}$ (link).

Recently, I also ran into $\Sigma_2^p$-complete $\mathtt{GENERALIZED\mbox{-}SUBSETSUM}$ problem (Page 16: Schaefer and Umans, 2008).

Do you know some other (non-trivial) interesting variants of SUBSETSUM problems? Specifically, $\Sigma_l^p$- or $\Pi_l^p$- complete problems for some $l > 1$.

Some definitions:

$\mathtt{UNARY\mbox{-}SUBSETSUM} = \{ 0^n \# 0^{i_1} \# \cdots\#0^{i_k} \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}i_j = n \}.$

$\mathtt{SUBSETSUM} = \{ S \# a_1 \# \cdots\# a_k \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}a_j = S \},$ where $S$ and $a_j$'s are binary numbers.

$\mathtt{GENERALIZED\mbox{-}SUBSETSUM} = \{ u \# v \# t \mid (\exists x) (\forall y) [ux+vy \neq t] \},$ where $u$ and $v$ are integer vectors, $t$ is an integer, and $x$ and $y$ are binary vectors of the same length as $u$ and $v$, respectively.

• one of my favorites is PIGEONHOLE-SUBSETSUM which is in TFNP (sciencedirect.com/science/article/pii/030439759190200L). Another interesting is EQUALITY-SUBSETSUM (sciencedirect.com/science/article/pii/S0022000001917842) – Marcos Villagra Jul 14 '12 at 13:19
• @MarcosVillagra: Thanks for your comment. PIGEONHOLE-SUBSETSUM looks interesting. Do you know any decision version of PIGEONHOLE-SUBSETSUM? – Abuzer Yakaryilmaz Jul 16 '12 at 13:39
• There is no decision version because the upper bound on the summation forces the problem to always have a solution, hence the decision version is trivial. The proof of it (that there is always a solution) is not difficult, is an application of the pigeonhole principle. This is a nice reference by Papadimitriou (cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf). – Marcos Villagra Jul 17 '12 at 1:22
• One big open problem is to prove if PIGEONHOLE-SUBSETSUM is complete for PPP. – Marcos Villagra Jul 17 '12 at 1:23
• @MarcosVillagra: Thank you for your further comments. What was in my mind is actually that "is there any nontrivial but still natural decision problem version of PIGEONHOLE-SUBSETSUM?". For example, one of the decision problem versions of integer factorization is as follows: given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 < d < M (en.wikipedia.org/wiki/Integer_factorization)? – Abuzer Yakaryilmaz Jul 17 '12 at 8:03

$$\mathtt{SUBSETSUM\mbox{-}GAME}=\{ S~ \forall(a_1 , b_1) \exists(e_1,f_1) \cdots \forall(a_n , b_n) \exists(e_n,f_n) \},$$ where
• $S$ and each $a_i,b_i,e_i$, and $f_i$ are natural numbers ($1 \leq i \leq n$); and,
• for every $x=(x_1,\ldots,x_n) \in \times_{i=1}^n \{ a_i,b_i \}$, there exists a $y=(y_1,\ldots,y_n) \in \times_{i=1}^n \{ e_i,f_i \}$ such that $S = \sum_{i=1}^n = x_i+y_i$.