8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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) $\endgroup$ – Marcos Villagra Jul 14 '12 at 13:19
  • $\begingroup$ @MarcosVillagra: Thanks for your comment. PIGEONHOLE-SUBSETSUM looks interesting. Do you know any decision version of PIGEONHOLE-SUBSETSUM? $\endgroup$ – Abuzer Yakaryilmaz Jul 16 '12 at 13:39
  • 2
    $\begingroup$ 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). $\endgroup$ – Marcos Villagra Jul 17 '12 at 1:22
  • 2
    $\begingroup$ One big open problem is to prove if PIGEONHOLE-SUBSETSUM is complete for PPP. $\endgroup$ – Marcos Villagra Jul 17 '12 at 1:23
  • $\begingroup$ @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)? $\endgroup$ – Abuzer Yakaryilmaz Jul 17 '12 at 8:03
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.