P not equal to NP
share
Let G(V,E) be a graph with vertex set V and edge set E, and let X be either V or E. Let Π be a search problem with input X and solution Y, where Y ⊆ X. Let Y' denote a sub-solution of Π. That is, Y' is the solution of Π when the input is X', the vertex or edge set of some minor G' of G. Consider the set system (X, I), where I denotes the family of all sub-solutions of Π. We prove that the problem Π belongs to P if and only if (X, 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 NP⊂P. Thus, P = NP.
READ FULL TEXT