patternMinor
Is there a $L$-complete variant of SAT?
Viewed 0 times
sattherevariantcomplete
Problem
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?
Solution
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.
Refining Schaefer’s Theorem.
Context
StackExchange Computer Science Q#141921, answer score: 5
Revisions (0)
No revisions yet.