The problem $⊕2SAT$ is defined as a problem where we need to find the parity of the number of solutions of $2$-$CNF$ formulae and is known to be $\oplus P$ complete.

I introduce the following variant of $⊕2SAT$:

In this variant we put the restriction on the input of the $⊕2SAT$ problem the restriction is that every input must contain all clauses that contain a specific variable ,for concretness ,let's say we put the restriction on the input such that every input must contain all 2-literal clauses that contains variable (a) .

I want to ask if this variant of variant remains $\oplus P$ complete.

I think this variant is $\oplus P$ complete ,my reasons are that the output of this type of problem is restricted to either true or false thus ,I think even if we apply the above restriction the input should be able to express any $⊕2SAT$ without changing the output of the $⊕2SAT$ instance.


1 Answer 1


This problem can be solved easily: trivially, the number of solutions is 0, so the parity is even.

Consider any other variable $b$. Then because the formula $\varphi$ must contain all clauses that contain the variable $a$, $\varphi$ must have the form

$$\varphi = (a \lor b) \land (a \lor \neg b) \land (\neg a \lor b) \land (\neg a \lor \neg b) \land \cdots$$

It is easy to see that no assignment can satisfy this formula. As such, it is very unlikely that the problem is $\oplus P$ complete.

The reasoning you give makes no sense to me. There are plenty of problems whose output are true or false but are not $\oplus P$ complete.

  • $\begingroup$ I forgot to mention that the version of $⊕2SAT$ I am referring to here is the positive $⊕2SAT$ which is also known to be $⊕P-complete$ .Sorry for the confusion .I've edited my post to include the missing details. $\endgroup$
    – Anuj
    Commented Mar 17, 2023 at 3:59
  • $\begingroup$ @Anuj, No worries. I know these things happen. I recommend you ask a new question, rather than changing your question to invalidate an existing answer, and that you proofread your questions carefully in the future. $\endgroup$
    – D.W.
    Commented Mar 17, 2023 at 6:42
  • $\begingroup$ Ok ,thanks for the advice. $\endgroup$
    – Anuj
    Commented Mar 17, 2023 at 7:14
  • $\begingroup$ I've edited this post as it originally was and posted a new question about variant of $positive -⊕2SAT$ here : cs.stackexchange.com/q/159090/157195 $\endgroup$
    – Anuj
    Commented Mar 17, 2023 at 7:19

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.