Theoretical Computer Science
cc.complexity-theory reference-request np-hardness polynomial-hierarchy subset-sum
Updated Thu, 16 Jun 2022 03:31:47 GMT

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):

\begin{equation} \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) \}, \end{equation} 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.


External Links

External links referenced by this document:

References