1-in-k-SAT problem is to determine if there’s an assignment to variables such that every clause has exactly one true literal. Is this problem known to be in P when restricted to positive literals, and atmost two occurrences of a variable?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What do you mean by "restricted to positive literals"? $\endgroup$– xskxzrCommented Jun 21 at 3:00
-
$\begingroup$ A literal can be a variable (positive literal) or its complement(negative literal). These instances do not have negative literals. $\endgroup$– AjayCommented Jun 23 at 12:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
For convenience, we call a clause containing variables with exact one occurrence a free clause. These variables with exact one occurrence in a free clause are called free variables.
To answer if an instance of the restricted SAT is satisfiable, we turn it into a graph. Each clause corresponds to a vertex in the graph. There is an edge between two vertices iff their corresponding clauses are both free clauses (we call such edges free edges for convenience) or they have common variables.
We assume the number of clauses are always even, otherwise we can add a free clause with only one new variable. It has no influence on the satisfiability of the original instance.
If the graph has a perfect matching, we can construct a satisfying assignment of the SAT instance from the matching: if an free edge is chosen in the perfect matching, the corresponding clauses are both free clauses, and for each clause we assign TRUE to one of its free variables to make both clauses satisfied; if a non-free edge is chosen in the perfect matching, the corresponding clauses share some common variables, and we assign TRUE to one of them to make both clauses satisfied. On the other hand, if the graph does not have a perfect matching, the SAT instance is not satisfiable. The proof is similar to the argument above and we omit it here.
As a conclusion, your problem is in P: we can solve it by constructing a graph and finding its maximum matching.
-
$\begingroup$ I think there’s a flaw in the proof. Suppose the max matching is not a perfect matching. And suppose all vertices not incident on matched edges correspond to free clauses. Then clearly there’s a solution to SAT instance. $\endgroup$– AjayCommented Jun 26 at 1:20
-
$\begingroup$ @Ajay "There is an edge between two vertices iff their corresponding clauses are both free clauses (we call such edges free edges for convenience) or they have common variables" the vertices corresponding to free clauses are connected to each other, so we can still add free edges to the matching in your example. $\endgroup$– xskxzrCommented Jun 26 at 2:41