L Versus Parity-L

EasyChair Preprint 3343

Abstract

A 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

@booklet{EasyChair:3343,
  author    = {Frank Vega},
  title     = {L Versus Parity-L},
  howpublished = {EasyChair Preprint 3343},
  year      = {EasyChair, 2020}}