HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is there a $L$-complete variant of SAT?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#141921, answer score: 5

Revisions (0)

No revisions yet.