<p>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$?</p>

<blockquote>
  <p>What is the complexity of Exactly $A$-SAT  ?</p>
</blockquote>

<p>Edit -- 
Some different cases seem interesting:</p>

<p>Let $A_{MAJ}=\{m\in\mathbb{N},2^{n-1} &lt; 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$.</p>

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

<p>($n$ is the number of variables of $F$).</p>

<p>Thank you for your answers and your comments. </p>

CC BY-SA 3.0
2011-11-22T07:03:50.870Z
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
CC BY-SA 3.0
2011-11-22T09:20:55.567Z
Right for the first and the second point - I have just edited the question according to your remarks- Tks !
Xavier Labouze
CC BY-SA 3.0
2011-11-22T21:54:59.573Z
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
CC BY-SA 3.0
2011-11-22T22:41:56.957Z
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
CC BY-SA 3.0
2011-11-24T18:19:04.753Z
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
CC BY-SA 3.0
2011-12-06T00:43:35.887Z
@SashoNikolov , What do you think about Ryan 's comment ? I think exactly $A_{MAJ}$-SAT is $PP$-complete , but it might be a question of encoding the set $A$.
Xavier Labouze
CC BY-SA 3.0
2011-12-06T03:15:07.267Z
Well I think that you should either take whatever definition seems more elegant to you, or better yet whatever definition lets you prove interesting theorems. I agree with @Ryan's comments. But I am a little bothered by how specifying $A$ in the input acts as padding. However, the question as he points out will be interesting in that case as well
Sasho Nikolov
CC BY-SA 3.0
2011-12-29T19:27:50.760Z
This problem is C_P complete.. No?
Tayfun Pay
<cc.complexity-theory><sat><counting-complexity><polynomial-hierarchy>
Complexity of Exactly $A$-SAT
Xavier Labouze
# Complexity of Exactly $A$-SAT

(Asked by: username_0 on 2011-11-11)

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.

**Tags:** cc.complexity-theory, sat, counting-complexity, polynomial-hierarchy

> **Comments:**
> **username_1**: 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?  
> **username_0**: Right for the first and the second point - I have just edited the question according to your remarks- Tks !  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: @SashoNikolov , What do you think about Ryan 's comment ? I think exactly $A_{MAJ}$-SAT is $PP$-complete , but it might be a question of encoding the set $A$.  
> **username_1**: Well I think that you should either take whatever definition seems more elegant to you, or better yet whatever definition lets you prove interesting theorems. I agree with @Ryan's comments. But I am a little bothered by how specifying $A$ in the input acts as padding. However, the question as he points out will be interesting in that case as well  
> **username_3**: This problem is C_P complete.. No?  

---

## 0 answers

