7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Nov 22 '11 at 7:03
  • $\begingroup$ Right for the first and the second point - I have just edited the question according to your remarks- Tks ! $\endgroup$ – Xavier Labouze Nov 22 '11 at 9:20
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Nov 22 '11 at 21:54
  • $\begingroup$ 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. $\endgroup$ – Xavier Labouze Nov 22 '11 at 22:41
  • 3
    $\begingroup$ 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. $\endgroup$ – Ryan Williams Nov 24 '11 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.