2019HAL (Le Centre pour la Communication Scientifique Directe)Open access

A Solution of the P versus NP Problem

Frank Vega

Open full text 0 citations

Abstract

$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$.

About this research paper

What this paper is about

$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$.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

$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$.

Key concepts: Mathematics, Class (philosophy), P versus NP problem, Combinatorics, Statement (logic), Certificate, NP-complete, Subset sum problem

Related papers

Back to paper searchBrowse research topicsOriginal source
A Solution of the P versus NP Problem — Research Paper | ScholarLens