P not equal to NP. (arXiv:1802.03028v1 [cs.CC])

Let $G(V,E)$ be a graph with vertex set $V$ and edge set $E$, and let $X$ be either $V$ or $E$. Let $\Pi$ be a search problem with input $X$ and solution $Y$, where $Y \subseteq X$. Let $Y'$ denote a sub-solution of $\Pi$. That is, $Y'$ is the solution of $\Pi$ when the input is $X'$, the vertex or edge set of some minor $G'$ of $G$. Consider the set system $(X, \mathcal{I})$, where $\mathcal{I}$ denotes the family of all sub-solutions of $\Pi$. We prove that the problem $\Pi$ belongs to $\mathcal{P}$ if and only if $(X, \mathcal{I})$ satisfies an extension of the Exchange Axiom of a greedoid (Augmentability) and the Partial Heredity Axiom of a greedoid (Accessibility). We then show that the Hamiltonian Cycle Problem satisfies Accessibility, but not Augmentability. Hence $\mathcal{NP} \not \subset \mathcal{P}$. Thus, $\mathcal{P} \not = \mathcal{NP}$.

from cs updates on arXiv.org http://ift.tt/2G1WEpF
//