# Complexity of a variant of the Subset Sum Problem (second level polynomial hierarchy)

What is the complexity class of the following variant of the SSP problem:

Input: set of integers $$\{x_1,\ldots,x_n\}$$, integer $$k$$ and integer $$T$$.

Output: Yes, if there exists a subset $$S\subseteq \{x_1,\ldots,x_n\}$$ for which: $$|S|= k$$ and $$\forall S'\subseteq \overline{S}$$ it holds that: $$\sum_{x_i \in S}x_i + \sum_{y_i \in S'}y_i\neq T$$

Clearly, the problem is in $$\Sigma^P_2$$, but how can we prove that the problem is also $$\Sigma^P_2$$-Hard? (if it is...)

A possible reduction maybe from the Generalized-Subset Sum problem, mentioned in Umans Compendium, which is $$\Sigma^P_2$$-Hard and is defined as follows:

Input: two vectors $$u$$ and $$v$$ of integers, and an integer $$T$$.

Output: Yes, if $$(\exists x) (\forall y) [ux+vy\neq T]$$ is true, where $$x$$ and $$y$$ are binary vectors in the same length as $$u$$ and $$v$$.

Although the two problems seem similar, I wasn't able to find a reduction that works.

• Have you tried concatenating u and v in the reduction? Another possibility is reducing from the QSAT2 problem. Commented Jan 7 at 15:10
• Yes, I have tried doing the reduction by concatenating $u$ and $v$ but it doesn't seem to work. What reduction do you think is possible from QSAT2? Commented Jan 7 at 15:43