# 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
Right for the first and the second point - I have just edited the question according to your remarks- Tks ! –  Xavier Labouze Nov 22 '11 at 9:20
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
Right again, tks for your comment - actually it is not the encoding part of A which interests me, let me edit the question again to specify my point. –  Xavier Labouze Nov 22 '11 at 22:41
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

This problem is complete for complexity class ${\rm \bf C_{=}P}$. A language $L$ is in Syntactic complexity class ${\rm \bf C_{=}P}$ defined in ${S75,W86}$ if there exists a polynomial $p$ and a polynomial-time predicate $R$ such that, for each $x$,

$x \in L \Leftrightarrow ||\{y| \ |y| = p(|x|) \wedge R(x, y)\}|| = 2^{p(|x|)-1}$

The alternate definition of ${\rm \bf C_{=}P}$ allows us to set the acceptance cardinality to be a polynomial time computable function $f(x)$ instead of being set to the half of the total number of possibilities.

The place of ${\rm \bf C_{=}P}$ in the complexity hierarchy is as follows ${\rm \bf ES} \subseteq {\rm \bf C_{=}P} \subseteq {\rm \bf PP}$.

J. Simon. On Some Central Problems of Computational Complexity. PhD thesis, Cornell University Ithaca, 1975.

K. Wagner. The complexity of combinatorial problems with succinct input representations. Acta Informatica, 23:225–256, 1986.

-
Tks for your answer. I didn't know the class $C_P$. I guess you mean the number of accepting states is equal to a given polytime function. Where can I read more about this class ? –  Xavier Labouze Jan 2 '12 at 22:25
It was Simon whom defined the class in 75... I think it was Wagner whom gave it the name C_P... K. Wagner. The complexity of combinatorial problems with succinct input representations. Acta Informatica, 23(3):325-358, 1986 –  Tayfun Pay Jan 4 '12 at 1:23
C_P is contained in PP... It was shown by Simon in 1975.. –  Tayfun Pay Jan 4 '12 at 1:25
I see, it is the same class as $C_=$. Tks. –  Xavier Labouze Jan 4 '12 at 12:23
What if the size of $A$ is sub exponential in the size of the formula ? I am not sure a polynomial number of calls to any $C_P$-complete problem would help. –  Xavier Labouze Jan 27 '12 at 0:31