0
$\begingroup$

In the paper "Hard Tiling Problems with Simple Tiles", 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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ No, it is NP-complete. Do you mean its counting counterpart? Anyway, there is a reference right in the question that you linked to: sciencedirect.com/science/article/pii/S0890540196900164 . $\endgroup$
    – Emil Jeřábek
    Commented Jan 20, 2020 at 9:41
  • $\begingroup$ @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. $\endgroup$
    – Cyriac Antony
    Commented Jan 21, 2020 at 16:32
  • $\begingroup$ @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. $\endgroup$
    – Cyriac Antony
    Commented Jan 21, 2020 at 16:33

1 Answer 1

Reset to default
2
$\begingroup$

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"?) suggest so!

Improve this answer
$\endgroup$
1
  • $\begingroup$ Shall I make this ans community wiki, or not? $\endgroup$
    – Cyriac Antony
    Commented Jan 20, 2020 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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