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.

Improve this question
$\endgroup$
5
  • 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
    Commented Jul 14, 2012 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
    Commented Jul 16, 2012 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
    Commented Jul 17, 2012 at 1:22
  • 2
    $\begingroup$ One big open problem is to prove if PIGEONHOLE-SUBSETSUM is complete for PPP. $\endgroup$
    – Marcos Villagra
    Commented Jul 17, 2012 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
    Commented Jul 17, 2012 at 8:03

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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