Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 6 down vote favorite
2

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$).

Thank you for your answers and your comments.

share|improve this question
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
2  
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
3  
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
show 3 more comments

1 Answer

up vote 1 down vote

This problem is exact counting and it is $C_{=}P$-complete. Counting complexity class ${\bf C_{=}P}$ asks whether or not the total number of accepting paths of a Non-deterministic polynomial time Turing machine equals a given polynomial time computable function f.

share|improve this answer
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.