| Peer-Reviewed

Problem of Recognition of Hamiltonian Graph

Received: 20 January 2016     Accepted: 3 February 2016     Published: 28 May 2016
Views:       Downloads:
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
  • 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
  • Department of Mathematics and Mathematical Modeling, Institute of Mathematics and Mechanics Named After Nikolai Ivanovich Lobachevsky, Kazan (Volga Region) Federal University, Kazan, Russia

  • Sections