A Solution of the P versus NP Problem
Frank Vega
Abstract
Frank Vega
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$.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
$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