Problem of Recognition of Hamiltonian Graph
Kochkarev Bagram Sibgatullovich · International Journal of Wireless Communications and Mobile Computing · 2016
In this article the author introduces the notions of combinatorial and of polynomial combinatorial sets in enumerative combinatorics. Formulates the problem of finding in combinatorial set of element with an easily recognizable property. The author proposes an efficient algorithm for solving this problem, which cancels known in the theory of algorithms abstract Turing, Church and Markov. We prove the criterion of polynomiality of the formulated problem. As a special case of this problem considers the problem of recognition of a Hamiltonian cycle in an undirected graph. We prove non-polynomiality this problem, which implies in particular the hypothesis of Jacques Edmonds P ≠NP.