L Versus Parity-L

EasyChair Preprint no. 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: complexity classes, logarithmic space, reduction, XOR-2SAT, XOR-3SAT

@Booklet{EasyChair:3343,
  author = {Frank Vega},
  title = {L Versus Parity-L},
  howpublished = {EasyChair Preprint no. 3343},

  year = {EasyChair, 2020}}