Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint . 2020
License: CC BY
Data sources: Datacite
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Preprint . 2020
License: CC BY
Data sources: ZENODO
addClaim

P versus NP

Authors: 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$? It was essentially mentioned in 1955 from a letter written by John Nash to the United States National Security Agency. However, 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. To attack the $P$ versus $NP$ question the concept of $\textit{NP-completeness}$ has been very useful. A well-known $\textit{NP-complete}$ problem is $3SAT$. In $3SAT$, it is asked whether a given Boolean formula $\phi$ in $3CNF$ is satisfiable. In this paper, we consider the problem of computing the sum of the weighted densities of states of a Boolean formula in $3CNF$. Given a Boolean formula $\phi$, the density of states $n(E)$ counts the number of truth assignments that leave exactly $E$ clauses unsatisfied in $\phi$. The weighted density of states $m(E)$ is equal to $E \times n(E)$. The sum of the weighted densities of states of a Boolean formula in $3CNF$ with $m$ clauses is equal to $\sum_{E = 0}^{m} m(E)$. We prove that we can calculate the sum of the weighted densities of states in polynomial time. Diophantine equations of the form $\sum_{E = 0}^{m} E \times x_{E} = c$ are solvable in polynomial time for arbitrary values of $m$. We can apply this Diophantine equation such that $c$ is the value of the sum of the weighted densities of states from a Boolean formula $\phi$ in $3CNF$, $E \times x_{E}$ is the value of each term $E \times n(E)$, where $n(E)$ corresponds to the unknown value of $x_{E}$. Hence, we only need to check that $\sum_{E = 1}^{m} E \times x_{E} = c$ has its positive solutions such that $\sum_{E = 1}^{m} x_{E} \neq 2^{n}$ is always true when $x_{j} > 0$, $j \leq E$ and $x_{E + 2} > 0$ implies that $x_{E + 1} > 0$ and when $x_{j} > 0$, $j \leq E$ and $x_{E + 1} = 0$ implies that $x_{E + 2} = 0$, where $n$ is the number of variables in $\phi$. That would be equivalent to prove the system of the two linear Diophantine equations $\sum_{E = 1}^{m} E \times x_{E} = c$ and $\sum_{E = 1}^{m} x_{E} = 2^{n}$ has not positive solutions with the following properties: when $x_{j} > 0$, $j \leq E$ and $x_{E + 2} > 0$ implies that $x_{E + 1} > 0$ and when $x_{j} > 0$, $j \leq E$ and $x_{E + 1} = 0$ implies that $x_{E + 2} = 0$. Certainly, if the Boolean formula $\phi$ has $n$ variables, then $\phi$ has exactly $2^{n}$ possible truth assignments. In this way, we are able to check whether the Boolean formula $\phi$ is satisfiable and obtain a solution for the problem $3SAT$ in polynomial time. If any $\textit{NP-complete}$ problem is in $P$, then every $NP$ problem can be decided by a polynomial time algorithm. Consequently, we show the complexity class $P$ is equal to $NP$.

Keywords

polynomial time, reduction, logarithmic space, complexity classes, one-way

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
    OpenAIRE UsageCounts
    Usage byUsageCounts
    visibility views 1
  • 1
    views
    Powered byOpenAIRE UsageCounts
Powered by OpenAIRE graph
Found an issue? Give us feedback
visibility
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
views
OpenAIRE UsageCountsViews provided by UsageCounts
0
Average
Average
Average
1
Green