4 ms·
Wait, this is very relevant to some work I’ve been doing recently, how do you conclude that Horn clauses should be preferred from Schaefer’s theorem?
by xavxav 3y ago
Wait, this is very relevant to some work I’ve been doing recently, how do you conclude that Horn clauses should be preferred from Schaefer’s theorem?
- thomasahle 3y agoIsn't it just that Horn clauses are easy to understand, and they are guaranteed to be fast.
- Karrot_Kream 3y agoTake a look at https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Schaefer's_dichotomy_theorem https://en.wikipedia.org/wiki/Boolean_satisfiability_problem... (based on Schaefer's "The complexity of satisfiability problems"). Horn clause satisfiability problems (HORN SAT) fall in P-c.
- xavxav 3y agoOh right this is just Horn clauses, not CHCs