Timeline for If a CNF contains only Horn and Xor clauses, then what is the complexity of determining Satisfiability?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 19, 2017 at 17:16 | vote | accept | csTheoryBeginner | ||
| Nov 19, 2017 at 17:08 | comment | added | csTheoryBeginner | @Yuval Filmus - I have to admit that I am very new to this field, as a result not aware of Schaeffer's theorem. The problem that motivated my question is from a CSP that has continuous variables, whose feasibility is reducible to a SAT. I have been unsuccessful in resolving its complexity with the problem described in CSP form, but have no clue on how to go about this in SAT form. | |
| Nov 19, 2017 at 16:53 | comment | added | Yuval Filmus | Have you tried either coming up with an algorithm or showing that the problem is NP-complete? | |
| Nov 19, 2017 at 16:52 | answer | added | Yuval Filmus | timeline score: 3 | |
| Nov 19, 2017 at 16:51 | comment | added | Yuval Filmus | What do you think? Have you tried applying Schaeffer's theorem to the bounded width case? | |
| Nov 19, 2017 at 16:22 | history | asked | csTheoryBeginner | CC BY-SA 3.0 |