Download PDFOpen PDF in browserL Versus Parity-LEasyChair Preprint 33434 pages•Date: May 7, 2020AbstractA major complexity classes are L and ⊕L (parity-L). A logarithmic space Turing machine has a read-only input tape, a write-only output tape, and some read/write work tapes. The work tapes may contain at most O(log n) symbols. L is the complexity class containing those decision problems that can be decided by a deterministic logarithmic space Turing machine. The complexity class ⊕L has the same relation to L as ⊕P does to P. Whether L = ⊕L is a fundamental question that it is as important as it is unresolved. We prove there is a complete problem for ⊕L that can be logarithmic space reduced to a problem in L. In this way, we demonstrate that L = ⊕L. Keyphrases: XOR-2SAT, XOR-3SAT, complexity classes, logarithmic space, reduction
|