Problem of Recognition of Hamiltonian Graph

Kochkarev Bagram Sibgatullovich

doi:doi:10.11648/j.wcmc.20160402.17

| Peer-Reviewed

Problem of Recognition of Hamiltonian Graph

Kochkarev Bagram Sibgatullovich

Published in International Journal of Wireless Communications and Mobile Computing (Volume 4, Issue 2)

Received: 20 January 2016 Accepted: 3 February 2016 Published: 28 May 2016

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

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.

Published in	International Journal of Wireless Communications and Mobile Computing (Volume 4, Issue 2)
DOI	10.11648/j.wcmc.20160402.17
Page(s)	52-55
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2016. Published by Science Publishing Group

Keywords

Polynomial Problem, NP-problem, NPC-problem, Hamiltonian Cycle, Hamiltonian Graph

References

[1]	Cobham A. The intrinsic computational difficulty of functions //In Procedings of the 1964 Congress for Logic, Methodology, and the Philosophy of Science.-North-Holland, 1964. - P. 24-30.
[2]	Edmonds J. Paths, trees and flowers //Canadian Journal of Mathematics.-1965-Vol. 17. - P. 449-467.
[3]	Cormen T. H., Leiserson Ch. E., Rivest R. L., Introduction to Algorithms, MIT Press, 1990. 2002. P. 955.
[4]	Cook S. A., The P versus NP Problem //Manuscript prepared for the Clay Mathematics Institute for the Millennium, April, 2000, www.cs.toronto.edusacook.
[5]	Razborov A. A. Theoretical Computer Science: vzglyad mathematica, http://old.Computerra.ru/offline/2001/379/6782.
[6]	Kochkarev B. S. Prilogenie monotonnykh funktsij algebry logiki k probleme Kuka, Nauka v Vuzakh: matematika, fizika, informatika, Tezisy dokladov Mejdunarodnoj nauchno-obrazovatelnoj konferentsii, 2009, pp. 274-275. (in Russian).
[7]	Kochkarev B. S., On Cook’s problem, http://www.math.nsc.ru/conference/malmeet/08/Abs.
[8]	Kochkarev B. S. About one class polynomial problems with not polynomial certificates //arxiv: 1210.7591v1 [math. CO] 29 Oct 2012/.
[9]	Kochkarev B. S., About one class polynomial problems with not polynomial certificates //Second International Conference “Claster Computing”CC2013 (Ukraine, Lviv, June 3-5, 2013) P. 99-100.
[10]	Kochkarev B. S., K probleme Kuka //Matematicheskoe obrazovanie v shkole I v Vuze v usloviyakh perekhoda na novye obrazovatelnye standarty. Materialy Vserossiyskoy nauchno-practicheskoy konferentsii s mejdunarodnym uchastiem. TGGPU, Kazan, 2010. s. 133-136 (in Russian).
[11]	The Clay Mathematics Institute www.Claymath.org.Millennium Prize Problems.
[12]	Kurosh A. G. Kurs vysshey algebry. Izd. F. -M. Literatury, M., 1962, 432. (in Russian).
[13]	Kochkarev B. S., Vzaimootnosheniya mejdu slojnostnymi klassami P, NP i NPC. Problems of modern science and education. 2015, 11 (41), s. 6-8 (in Russian).
[14]	Kochkarev B. S., Dokazatelstvo gipotezy Edmondsa i reshenie problemy Kuka. Nauka, Tekhnika i Obrazovanie, 2014, 2 (2), s. 6-9. (in Russian).
[15]	Ravenstvo klassov P i NP https://ru.wikipedia.org/wiki.
[16]	En waarmee toverde het internet vandaag een lach op Uwge https://www.uscki.nl.
[17]	Gipoteza J. Edmondsa i problema S. A. Kuka http://www.refereed.ru.
[18]	Cook S. A. The complexity of theorem proving procedures. //In Proceedings of the Third Annual ACM Symposium on Theory of Computing. P. 151-158, 1971.
[19]	Levin L. A. Universal sorting problems. //Problemy Peredachi Informatsii, 9(3), s. 265-266, 1973.
[20]	Kochkarev B. S. Proof of the hypothesis Edmonds’s, not polynomial of NPC problems and classification of the problems with polynomial certificates.//arxiv: 1303.2580v1 [cs. CC] 7 Mar 2013.
[21]	Karp R. M. Reducibility among combinatorial problems. //In Raymond E. Miller and James W. Thatcher, editors, Complexity of computer Computations, P. 85-103, Plenum Press, 1972.
[22]	Stanley R. P. Enumerative Combinatorics v. 1, 1986.
[23]	Kochkarev B. S. Ob odnom algoritme, ne soglasuyutchemsya s tezisami Turinga, Churcha i Markova, Problems of modern science and education, M., 2014, 3(21) c. 23-25 (in Russian).
[24]	Kochkarev B. S. Gipoteza J. Edmondsa i problema S. A. Kuka. //Vestnik TGGPU, 2011 2 (24) s. 23-24 (in Russian).
[25]	Razborov A. A., Rudich S. Natural proof. Proceedings of the 26 th Annual ACM Symposium on the Theory of Computing. P. 204-213 DOI: 10.1145/195058.195134.
[26]	Babay priblizilsya k resheniyu pronlemy tysyacheletiya. http://lenta.ru/news/2015/11/20/graphtheory/.

Cite This Article

Plain Text BibTeX RIS

APA Style

Kochkarev Bagram Sibgatullovich. (2016). Problem of Recognition of Hamiltonian Graph. International Journal of Wireless Communications and Mobile Computing, 4(2), 52-55. https://doi.org/10.11648/j.wcmc.20160402.17

Copy | Download

ACS Style

Kochkarev Bagram Sibgatullovich. Problem of Recognition of Hamiltonian Graph. Int. J. Wirel. Commun. Mobile Comput. 2016, 4(2), 52-55. doi: 10.11648/j.wcmc.20160402.17

Copy | Download

AMA Style

Kochkarev Bagram Sibgatullovich. Problem of Recognition of Hamiltonian Graph. Int J Wirel Commun Mobile Comput. 2016;4(2):52-55. doi: 10.11648/j.wcmc.20160402.17

Copy | Download

@article{10.11648/j.wcmc.20160402.17,
  author = {Kochkarev Bagram Sibgatullovich},
  title = {Problem of Recognition of Hamiltonian Graph},
  journal = {International Journal of Wireless Communications and Mobile Computing},
  volume = {4},
  number = {2},
  pages = {52-55},
  doi = {10.11648/j.wcmc.20160402.17},
  url = {https://doi.org/10.11648/j.wcmc.20160402.17},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.wcmc.20160402.17},
  abstract = {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.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - Problem of Recognition of Hamiltonian Graph
AU  - Kochkarev Bagram Sibgatullovich
Y1  - 2016/05/28
PY  - 2016
N1  - https://doi.org/10.11648/j.wcmc.20160402.17
DO  - 10.11648/j.wcmc.20160402.17
T2  - International Journal of Wireless Communications and Mobile Computing
JF  - International Journal of Wireless Communications and Mobile Computing
JO  - International Journal of Wireless Communications and Mobile Computing
SP  - 52
EP  - 55
PB  - Science Publishing Group
SN  - 2330-1015
UR  - https://doi.org/10.11648/j.wcmc.20160402.17
AB  - 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.
VL  - 4
IS  - 2
ER  -

Copy | Download

Author Information

Kochkarev Bagram Sibgatullovich

Department of Mathematics and Mathematical Modeling, Institute of Mathematics and Mechanics Named After Nikolai Ivanovich Lobachevsky, Kazan (Volga Region) Federal University, Kazan, Russia

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Kochkarev Bagram Sibgatullovich. (2016). Problem of Recognition of Hamiltonian Graph. International Journal of Wireless Communications and Mobile Computing, 4(2), 52-55. https://doi.org/10.11648/j.wcmc.20160402.17

Copy | Download

ACS Style

Kochkarev Bagram Sibgatullovich. Problem of Recognition of Hamiltonian Graph. Int. J. Wirel. Commun. Mobile Comput. 2016, 4(2), 52-55. doi: 10.11648/j.wcmc.20160402.17

Copy | Download

AMA Style

Kochkarev Bagram Sibgatullovich. Problem of Recognition of Hamiltonian Graph. Int J Wirel Commun Mobile Comput. 2016;4(2):52-55. doi: 10.11648/j.wcmc.20160402.17

Copy | Download

@article{10.11648/j.wcmc.20160402.17,
  author = {Kochkarev Bagram Sibgatullovich},
  title = {Problem of Recognition of Hamiltonian Graph},
  journal = {International Journal of Wireless Communications and Mobile Computing},
  volume = {4},
  number = {2},
  pages = {52-55},
  doi = {10.11648/j.wcmc.20160402.17},
  url = {https://doi.org/10.11648/j.wcmc.20160402.17},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.wcmc.20160402.17},
  abstract = {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.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - Problem of Recognition of Hamiltonian Graph
AU  - Kochkarev Bagram Sibgatullovich
Y1  - 2016/05/28
PY  - 2016
N1  - https://doi.org/10.11648/j.wcmc.20160402.17
DO  - 10.11648/j.wcmc.20160402.17
T2  - International Journal of Wireless Communications and Mobile Computing
JF  - International Journal of Wireless Communications and Mobile Computing
JO  - International Journal of Wireless Communications and Mobile Computing
SP  - 52
EP  - 55
PB  - Science Publishing Group
SN  - 2330-1015
UR  - https://doi.org/10.11648/j.wcmc.20160402.17
AB  - 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.
VL  - 4
IS  - 2
ER  -

Copy | Download