Search

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.

$P$ versus $NP$ is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is $P$ equal to $NP$? A precise statement of the $P$ versus $NP$ problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. A major complexity classes are $L$ and $\oplus L$. A logarithmic 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 Turing machine. The complexity class $\oplus L$ has the same relation to $L$ as $\oplus P$ does to $P$. We demonstrate there is a complete problem for $\oplus L$ that can be logarithmic space reduced to a problem in $L$. Consequently, we show $L = \oplus L$. To attack the $P$ versus $NP$ problem, the $\textit{NP--completeness}$ is a useful result. We demonstrate the result $L = \oplus L$ implies there is a well-known $\textit{NP--complete}$ in $P$. In this way, we guarantee the complexity class $P$ is equal to $NP$.

A major complexity classes are $L$, $POLYLOGTIME$ and $\oplus L$. A logarithmic Turing machine has a read-only input tape, a write-only output tape, and some read/write work tapes. The work tapes may contain $O(\log n)$ symbols. $L$ is the complexity class containing those decision problems that can be decided by a deterministic logarithmic Turing machine. We define the complexity class $POLYLOGTIME$ as the problems which can be decided by a random access machine in poly-logarithmic time. We prove there is problem in the complexity class $L$ which cannot be solved by a random access machine in poly-logarithmic time. Hence, we show $L \nsubseteq POLYLOGTIME$. The complexity class $\oplus L$ has the same relation to $L$ as $\oplus P$ does to $P$. We demonstrate there is a complete problem for $\oplus L$ that can be logarithmic space reduced to a problem in $L$. Consequently, we show $L = \oplus L$.