# Complexity of Exactly $A$-SAT

Let define the "Exactly $A$-SAT" problem : Given a CNF formula $F$ and a set $A$ of positive integers, is it true that the number of models of $F$ is in $A$?

What is the complexity of Exactly $A$-SAT ?

Edit -- Some different cases seem interesting:

Let $A_{MAJ}=\{m\in\mathbb{N},2^{n-1} < m\leq2^{n}\}$, then Exactly $A_{MAJ}$-SAT corresponds to the canonical $PP$-complete MAJ-SAT (Given a CNF formula $F$, is it true that $F$ is satisfied by more than half of the possible variable assignments?) - as long as $A_{MAJ}$ is not considered as part of the input, otherwise, as @Ryan's comment underlines it, the problem is in $P$.

Let $A_{SAT}=\{m\in\mathbb{N},1 \leq m\leq2^{n}\}$, then Exactly $A_{SAT}$-SAT is simply SAT.

($n$ is the number of variables of $F$).

• To justify the subscript MAJ, you probably should make the inequalities in the definition of $A_{MAJ}$ be $2^{n-1} < m \leq 2^n$. In that case, Exact $A_{MAJ}$-SAT seems to be precisely MAJSAT, I don't see why you need a reduction. I do not understand the claim about "falling in P": the problem is PP-complete, what do you define by extension, and what is in P? – Sasho Nikolov Nov 22 '11 at 7:03
• Saying that Ex-$A$-SAT is easy when $A$ has high Kolmogorov complexity is IMHO misleading. It's not that the satisfiability problem itself is easy, but rather you're giving the algorithm additional time, proportional to the complexity of $A$. Give $A$ as an oracle rather than an encoding, and the problem should be harder for more complex $A$. Also I don't see anything interesting about saying that MAJSAT is easy if you put $\Omega(2^n)$ redundant bits in every input. – Sasho Nikolov Nov 22 '11 at 21:54
• If Exactly $A_{MAJ}$-SAT is supposed to be $PP$-complete (and Exactly $A_{SAT}$-SAT is supposed to be $NP$-complete) then the set $A_{MAJ}$ should not be considered as part of the input (otherwise, the input length will be $2^n$, so the problem is in $P$). The problem is interesting even if $A$ is part of the input: for instance, by Valiant-Vazirani, there is a randomized reduction from SAT to Exactly $A$-SAT. – Ryan Williams Nov 24 '11 at 18:19