<p>The main credit should go to <strong>John Fearnley</strong>!</p>

<p>Here is a PSPACE-complete problem given in <a href="http://dx.doi.org/10.1007/978-3-642-39212-2_21" rel="nofollow">(John Fearnley, Marcin Jurdzinski: Reachability in Two-Clock Timed Automata Is PSPACE-Complete. ICALP (2) 2013: 212-223)</a>:</p>

<p>\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 </p>

<ul>
<li>$S$ and each $ a_i,b_i,e_i $, and $f_i$ are natural numbers ($1 \leq i \leq n$); and,</li>
<li>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 $.</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2014-03-10T23:17:22.070Z
2014-03-10T23:17:22.070Z
Abuzer Yakaryilmaz
<p>I know the following variants of SUBSETSUM problems: $ \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} $ (<a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5670819" rel="nofollow noreferrer">Elberfeld at. al., 2010</a>), NP-complete $ \mathtt{SUBSETSUM} $, and NEXP-complete $ \mathtt{SUCCINCT\mbox{-}SUBSETSUM} $ (<a href="https://cstheory.stackexchange.com/a/3303/7358">link</a>). </p>

<p>Recently, I also ran into $ \Sigma_2^p $-complete $ \mathtt{GENERALIZED\mbox{-}SUBSETSUM} $ problem (<a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CFkQFjAA&amp;url=http://ovid.cs.depaul.edu/documents/phcom.ps&amp;ei=M4IAULzUC8Te4QTRmsWCCA&amp;usg=AFQjCNGqacj8opgRw32nxe0nRPpGi0A0_g&amp;sig2=cHvaw8vS_8l63zs5XsD0bA" rel="nofollow noreferrer">Page 16: Schaefer and Umans, 2008</a>).</p>

<p>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 &gt; 1 $.</p>

<hr>

<p>Some definitions:</p>

<p>$
\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 \}.
$</p>

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

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

CC BY-SA 3.0
2012-07-14T13:19:03.473Z
one of my favorites is PIGEONHOLE-SUBSETSUM which is in TFNP (http://www.sciencedirect.com/science/article/pii/030439759190200L). Another interesting is EQUALITY-SUBSETSUM (http://www.sciencedirect.com/science/article/pii/S0022000001917842)
Marcos Villagra
CC BY-SA 3.0
2012-07-16T13:39:58.137Z
@MarcosVillagra: Thanks for your comment. PIGEONHOLE-SUBSETSUM looks interesting. Do you know any decision version of PIGEONHOLE-SUBSETSUM?
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-07-17T01:22:20.007Z
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 (http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf).
Marcos Villagra
CC BY-SA 3.0
2012-07-17T01:23:09.473Z
One big open problem is to prove if PIGEONHOLE-SUBSETSUM is complete for PPP.
Marcos Villagra
CC BY-SA 3.0
2012-07-17T08:03:29.913Z
@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 (http://en.wikipedia.org/wiki/Integer_factorization)?
Abuzer Yakaryilmaz
<cc.complexity-theory><reference-request><np-hardness><polynomial-hierarchy><subset-sum>
Interesting SUBSET-SUM problems
Abuzer Yakaryilmaz
# Interesting SUBSET-SUM problems

(Asked by: username_0 on 2012-07-13)

I know the following variants of SUBSETSUM problems: $ \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} $ ([Elberfeld at. al., 2010](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5670819)), NP-complete $ \mathtt{SUBSETSUM} $, and NEXP-complete $ \mathtt{SUCCINCT\mbox{-}SUBSETSUM} $ ([link](https://cstheory.stackexchange.com/a/3303/7358)).

Recently, I also ran into $ \Sigma\_2^p $-complete $ \mathtt{GENERALIZED\mbox{-}SUBSETSUM} $ problem ([Page 16: Schaefer and Umans, 2008](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CFkQFjAA&url=http://ovid.cs.depaul.edu/documents/phcom.ps&ei=M4IAULzUC8Te4QTRmsWCCA&usg=AFQjCNGqacj8opgRw32nxe0nRPpGi0A0_g&sig2=cHvaw8vS_8l63zs5XsD0bA)).

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.

**Tags:** cc.complexity-theory, reference-request, np-hardness, polynomial-hierarchy, subset-sum
> **Comments:**
> **username_1**: one of my favorites is PIGEONHOLE-SUBSETSUM which is in TFNP (http://www.sciencedirect.com/science/article/pii/030439759190200L). Another interesting is EQUALITY-SUBSETSUM (http://www.sciencedirect.com/science/article/pii/S0022000001917842)  
> **username_0**: @MarcosVillagra: Thanks for your comment. PIGEONHOLE-SUBSETSUM looks interesting. Do you know any decision version of PIGEONHOLE-SUBSETSUM?  
> **username_1**: 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 (http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf).  
> **username_1**: One big open problem is to prove if PIGEONHOLE-SUBSETSUM is complete for PPP.  
> **username_0**: @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 (http://en.wikipedia.org/wiki/Integer_factorization)?  

---

## 1 answers

### Answer by username_0 on 2014-03-10. Score: 1 | Accepted answer

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)](http://dx.doi.org/10.1007/978-3-642-39212-2_21):

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


---

