Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP

Question

I want to know if finding solution to a specific number of 2SAT equations sepearted by OR gate (DNF form as below) is in P or NP.

The equation has total n variables and each clause is a 2SAT equation in itself in a subset of variables from 1 to n. Example:

F = [(x1 || x2 ) && ( !x2 || x3) && (x3 || x4)] || [(x2 || x5) && (x3 || x6) && (!x4 || !x6)] || ....

The equation F is a DNF of 2SAT equations, which has say m clauses. Is finding a solution to this in NP? If yes how?

Also, specifically I also want to know if finding False instances of equation F is in P or NP as well.

Answer 1

• First, let me note that the question's title is a bit misleading, because $P$ is a subset of $NP$. See also Yuval Filmus's comment. I assume what you intended to ask is whether it's in $P$ or in $NP \setminus P$.
• Also, the name "DNF" specifically refers to a disjunction of elementary conjunctions, not a disjunction of arbitrary functions. What you are describing is not a DNF, but a disjunction of CNFs.

With that out of the way, here's my answer.

---

1. To satisfy a disjunction of 2-CNFs, all you need is to satisfy one of them. So, if you apply the 2-SAT algorithm to the first of the CNFs and get a "yes", then the answer to the whole problem is "yes". Otherwise, you just move on to the second one, and so on. Shouldn't take long, since you only have m of them. If none of them can be satisfied individually, i.e. they are all constant zeroes, then obviously the entire thing is a constant zero.

   So the answer to the first part is: the problem is in P, with the following decision algorithm:

   For every 2-CNF, apply the "normal" 2-SAT algorithm (the resolution rule) to determine if it's satisfiable or not. If "yes", just return "yes". If you went through all of them without finding a "yes", then return "no".

---

2. Now, finding the "False" cases of that formula (also known as the problem of tautology) is another question entirely. For one thing, tautology for ORs of ANDs of ORs is equivalent to satisfiability for ANDs of ORs of ANDs, by De Morgan's rule. But that's just a more general case of an already general SAT problem, isn't it?

   Consider what happens when you restrict the set of possible formulas to those in which every two-element disjunction is really just one element, repeated. So it is a formula like $$ F = [(x_1 \vee x_1 ) \& ( \neg x_2 \vee \neg x_2) \& (x_3 \vee x_3)] \vee [(x_2 \vee x_2) \& (x_4 \vee x_4) \& (x_5 \vee x_5)] \vee ... $$ which is equivalent to $$ F = [x_1 \& \neg x_2 \& x_3] \vee [x_2 \& x_4 \& x_5] \vee ... $$ which is just a normal DNF. After the De Morgan transformation, you get a normal CNF, whose satisfiability is known to be NP-hard. Therefore, any problem that includes this one as a subset will also be at least NP-hard.

   Obviously, the problem in question won't be outside NP, because it is still polynomially verifiable. So the answer to your second question is "in NP, but not in P".