Theoretical Computer Science

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.

Solution

The main credit should go to John Fearnley!

Here is a PSPACE-complete problem given in (John Fearnley, Marcin Jurdzinski: Reachability in Two-Clock Timed Automata Is PSPACE-Complete. ICALP (2) 2013: 212-223):

$$\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$.

Similarly, we can define some complete problems for each level of polynomial hierarchy (PH). But, of course, in case of being complete at some level of PH, we need to release the condition of having only two natural numbers after each quantifier.