4
$\begingroup$

Many complete problem of different class of complexity has SAT variant. Like 3-SAT or $k$-SAT is $NP$-complete, Horn-SAT is $P$-complete, 2-SAT is $NL$-complete, and so on. So I was wondering if there is a $L$-complete variant of SAT?

$\endgroup$

1 Answer 1

5
$\begingroup$

The standard example is the variant of SAT in which each clause has the form $x$ or $y \oplus z$ (not allowing negations). For more examples, check Allender, Bauland, Immerman, Schnoor and Vollmer, The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.