Q: 3-cnf-sat with a twist question If you change the 3-cnf-sat problem as follows:
For each ci, ci = -xi1 OR -xi2 OR xi3 meaning exactly one of the variables appears without a negation.
You are also given values (0 or 1) to some (or all) of the x's.
You should be able to solve the problem (finding values of the x's that satisfy the problem or prove that it is unsatisfiable) in polynomial time.


*

*What is a polynomial running time algorithm that solves this problem?

*Prove that it runs in polynomial time.


hint: show that ci = -xi1 OR -xi2 OR xi3 is equal to c = (xi1 AND -xi2) -> xi3

A: The formulas you describe are a subset of Horn formulas. The satisfiability problem is thus no harder than Horn satisfiability and admits the same linear-time solution.
