<p>Yes, the counting version of 1-in-3 Sat is <span class="math-container">$\#P$</span>-complete. This is stated in "Complexity of Generalized Satisfiability Counting Problems" (Example 3.1), the reference pointed out by Emil in the comment.</p>

<p>Note:
This leads us to the curious question: is the counting version of every NP-complete problem <span class="math-container">$\#P$</span>-complete? The answers to this question (<a href="https://cstheory.stackexchange.com/q/16119/47855">When does &quot;X is NP-complete&quot; imply &quot;#X is #P-complete&quot;?</a>) suggest so!</p>

CC BY-SA 4.0
2020-01-20T10:56:11.443Z
Shall I make this ans community wiki, or not?
Cyriac Antony
CC BY-SA 4.0
2020-01-20T10:55:35.357Z
2020-01-20T12:21:29.830Z
2020-01-20T12:21:29.830Z
Cyriac Antony
<p>In the paper "<a href="https://link.springer.com/article/10.1007%2Fs00454-001-0047-6" rel="nofollow noreferrer">Hard Tiling Problems with Simple Tiles</a>", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat.</p>

<p><strong>Cubic Planar Positive 1-in-3 Satisfiability</strong><br>
<em>Instance</em>: A boolean formula <span class="math-container">$B=(X,C)$</span> where <span class="math-container">$X$</span> is a set of variables, <span class="math-container">$C$</span> a set of 3-element subsets over <span class="math-container">$X$</span> (clauses), and graph of B is a cubic planar graph.<br>
<em>Question</em>: Does there exist a truth assignment for <span class="math-container">$X$</span> such that each clause is <span class="math-container">$C$</span> has exactly one true variable?  </p>

<p>(see the note of the <a href="https://cstheory.stackexchange.com/a/42605/47855">https://cstheory.stackexchange.com/a/42605/47855</a> regarding terminology)</p>

<p>Then they prove that a particular tiling problem is NP-complete by a reduction from Cubic Planar Positive 1-in-3 Sat. 
The following note is given after their reduction:</p>

<blockquote>
  <p>While the reduction from this version of SAT to the tiling problem we gave in the previous section is parsimonious, this does not show that the counting problem is #P-complete, since we do not have such a result for Cubic Planar Positive 1-in-3 SAT. We leave this as an open problem for the reader.</p>
</blockquote>

<p>This gave me the impression that the counting version of 1-in-3 Sat is indeed #P-complete, but I couldn't find any source claiming this. <strong>Is the counting version of 1-in-3 Sat #P-complete?</strong></p>

CC BY-SA 4.0
2020-01-20T09:41:44.677Z
No, it is NP-complete. Do you mean its counting counterpart? Anyway, there is a reference right in the question that you linked to: https://www.sciencedirect.com/science/article/pii/S0890540196900164 .
Emil Jeřábek
CC BY-SA 4.0
2020-01-21T16:32:31.520Z
@Gamow, I don't understand why you remove the alternate names of the problem 1-in-3 Sat from the title. Many authors use the names Exactly one 3-sat and XSAT. If you are so sure it doesn't belong in the title, please consider adding these alternate names in the body of the question.
Cyriac Antony
CC BY-SA 4.0
2020-01-21T16:33:36.493Z
@EmilJeřábeksupportsMonica  You are welcome to expand your comment into an answer. (I shall remove my answer after that.) I didn't realise that i forgot to explicitly state that it is the counting version i am talking about.
Cyriac Antony
<cc.complexity-theory><np-hardness><counting-complexity>
Is the counting version of 1-in-3 Sat #P-complete?
Cyriac Antony
# Is the counting version of 1-in-3 Sat #P-complete?

(Asked by: username_0 on 2020-01-20)

In the paper "[Hard Tiling Problems with Simple Tiles](https://link.springer.com/article/10.1007%2Fs00454-001-0047-6)", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat.

**Cubic Planar Positive 1-in-3 Satisfiability**  
*Instance*: A boolean formula $B=(X,C)$ where $X$ is a set of variables, $C$ a set of 3-element subsets over $X$ (clauses), and graph of B is a cubic planar graph.  
*Question*: Does there exist a truth assignment for $X$ such that each clause is $C$ has exactly one true variable?

(see the note of the <https://cstheory.stackexchange.com/a/42605/47855> regarding terminology)

Then they prove that a particular tiling problem is NP-complete by a reduction from Cubic Planar Positive 1-in-3 Sat.
The following note is given after their reduction:

> While the reduction from this version of SAT to the tiling problem we gave in the previous section is parsimonious, this does not show that the counting problem is #P-complete, since we do not have such a result for Cubic Planar Positive 1-in-3 SAT. We leave this as an open problem for the reader.

This gave me the impression that the counting version of 1-in-3 Sat is indeed #P-complete, but I couldn't find any source claiming this. **Is the counting version of 1-in-3 Sat #P-complete?**

**Tags:** cc.complexity-theory, np-hardness, counting-complexity
> **Comments:**
> **username_1**: No, it is NP-complete. Do you mean its counting counterpart? Anyway, there is a reference right in the question that you linked to: https://www.sciencedirect.com/science/article/pii/S0890540196900164 .  
> **username_0**: @Gamow, I don't understand why you remove the alternate names of the problem 1-in-3 Sat from the title. Many authors use the names Exactly one 3-sat and XSAT. If you are so sure it doesn't belong in the title, please consider adding these alternate names in the body of the question.  
> **username_0**: @EmilJeřábeksupportsMonica  You are welcome to expand your comment into an answer. (I shall remove my answer after that.) I didn't realise that i forgot to explicitly state that it is the counting version i am talking about.  

---

## 1 answers

### Answer by username_0 on 2020-01-20. Score: 2 | Accepted answer

Yes, the counting version of 1-in-3 Sat is $\#P$-complete. This is stated in "Complexity of Generalized Satisfiability Counting Problems" (Example 3.1), the reference pointed out by Emil in the comment.

Note:
This leads us to the curious question: is the counting version of every NP-complete problem $\#P$-complete? The answers to this question ([When does "X is NP-complete" imply "#X is #P-complete"?](https://cstheory.stackexchange.com/q/16119/47855)) suggest so!

> **Comments:**
> **username_0**: Shall I make this ans community wiki, or not?  

---

