Consider the following problem:
for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation
define is it true that
for every $S \subseteq \{1, ..., 2n \}$ such that $|S|=n$ there exists $H \subseteq S$ such that
$$\sum_{i \in H} a_i = A. $$
This problem belongs to coNP. Indeed, for fixed $S$ we can define the existence of required $H$ in polynomial time since there exists a pseudo-polynomial algorithm for SUBSET-SUM.
Question: Is this problem coNP-complete?
UPD I have understood that a hardness result about this problem would give a partial answer to Stefan Szeider's question that he asked in his paper Monadic Second Order Logic on Graphs with Local Cardinality Constraints.
At this paper the author generalized Courcelle’s theorem by the following way:
We consider problems of the following form: Given a graph $G$ and for each vertexv of $G$ set $\alpha(v)$ of non-negative integers. The question is whether there exists a set $S$ of vertices or edges of $G$ that
(i) satisfies a fixed MSO-expressible property, and
(ii) for each vertex $v$ of $G$, the number of vertices in $S$ adjacent to $v$ plus the number of edges in $S$ incident with $v$ belongs to the set $\alpha(v)$. We call such a problem an MSO problem for graphs with local cardinality constraints,or MSO-LCC problem, for short.
The main result of the paper is the following theorem.
Theorem For every constant $k \ge 1$, every MSO-LCC problem can be solved in polynomial time for graphs of treewidth at most $k$.
It is natural to consider more general question.
We consider the more general class of Q-MSO-LCC problems where cardinality constraints are applied to second-order variablesthat are arbitrarily quantified (not just existentially as for MSO-LCC problems). We show, however, that there exist Q-MSO-LCC problems that are already NP-hard for graphs of treewidth $2$.
However, the example of an NP-hard problem that can be expressed as Q-MSO-LCC requires two alternations of quantifies. We do not know an example of NP-hard problem that can be expressed as Q-MSO-LCC problem with one alternation of quantifies.
I claim that unary $\Pi_2$-SUBSETSUM can be expressed as Q-MSO-LCC problem with one alternation of quantifies. For given $a_1, a_2, a_3,..., a_{2n}$ and
$A$
consider the graph with $a_1, a_2, a_3,..., a_{2n} + 2n + 2$ vertices:
Now let $X_1$ be a set of vertices that is some subset of vertices of the second (children of $R$) and the third levels with the following property: If a vertex $v$ of the second level belongs to $X_1$ then all children of $v$ belong to $X_1$. We require that $X_1$ contains $n$ vertices of the second level (so, $R$ has $n$ neighborhoods in $X_1$).
Let $X_2$ be some subset of $X_1$ with the same property: if a vertex $v$ of the second level belongs to $X_2$ then all children of $v$ belong to $X_2$. We require that $X_2$ contains $A$ vertices of the third level (so, $T$ has $A$ neighborhoods in $X_2$).
I claim that $(a_1,..., a_{2n}, A)$ belongs to $\Pi_2$-unary-subsetsum iff for all $X_1$ there exists $X_2$ with all properties written above.
