Do Hard SAT-Related Reasoning Tasks Become Easier in the Krom Fragment?

Nadia Creignou, Reinhard Pichler, Stefan Woltran

Many reasoning problems are based on the problem of satisfiability (SAT). While SAT itself becomes easy when restricting the structure of the formulas in a certain way, the situati…