+1 Recommend
1 collections
    • Record: found
    • Abstract: found
    • Article: found
    Is Open Access

    Polynomial solvability of NP-complete problems

    Read this article at

        There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


        A polynomial algorithm for solving the “Hamiltonian circuit” problem is presented in the paper. Computational complexity of the algorithm is equal to O(n8log22n), where n is the cardinality of the observed graph vertex set. Thus, the polynomial solvability for NP-complete problems is proved.

        Related collections

        Most cited references 1

        • Record: found
        • Abstract: not found
        • Article: not found

        Expressing combinatorial optimization problems by Linear Programs


          Author and article information

          [1 ]Department of Computational Mathematics and Software Engineering, South Ural State University, 76, Lenin prospect, Chelyabinsk 454080, Russia
          Author notes
          [* ]Corresponding author's e-mail address: anatoly.panyukov@
          (View ORCID Profile)
          ScienceOpen Research
          16 December 2014
          : 0 (ID: c0597241-52c2-47a7-8af0-dd09bbb57888 )
          : 0
          : 1-6
          © 2014 A. Panyukov.

          This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at .

          Figures: 1, Tables: 0, References: 9, Pages: 6
          Original article


          This is a pretty bold claim. Have you done any works towards a sample implementation? It would be relatively straightforward to test whether you arrive at the correct solution for random sample problems using the step number given in (7.4) and significant bit counts as given in the text with an arbitrary precision math library like e.g. GMP. Btw: Typo in sect. 5 ("elaxed") and formula (4.3) (you probably mean V(G)?) Also, what is the complexity of finding \lambda^0 and R?
          2015-02-04 14:03 UTC
          Indeed in the formula (4.3) should write V (G), and at the beginning of the 8-th row of section 5 should be "relaxed" instead of "elaxed". To encode the number $n=|V(G)| $ requires no more than $\log_2 n$ bits. Therefore, the complexity of computing the values of $M$, $\lambda^0$, and $R$ (see Proposition 8.3) does not exceed the value of the $O(log_2^2 n)$. Numerical experiment based on the subgradient algorithm for problem (6.3) was conducted. Assessment of its computational complexity above, but it allows you to use the 64 bit arithmetic for problems with n < 30.
          2015-02-11 03:38 UTC
          There are no comments.
          2015-02-03 16:33 UTC
          It necessary all symbols $C$ to replace by symbol $F$ in the formula following formula (5.2).
          2015-01-30 16:25 UTC
          Let me answer the editorial comments: AQ1 Please provide missing department name for author affiliation. Department of Computational Mathematics and Software Engineering AQ2 Please provide missing editor names for reference “1”. Michael A. Harrison, and Ranan B. Banerji, and Jeffrey D. Ullman AQ3 Please provide missing editor names for reference “2”. R. E. Miller, and J. W. Thatcher, Eds., AQ4 Please provide an English translation of the book title in the reference “5”, as per journal style. Mathematical Programming: Theory and Algorithms (in French) AQ5 Please provide missing city for the “9” references list entry North Holland – Amsterdam Let me draw the attention of the editor at the incorrect display formula 8.7 on page. 3.
          2015-01-07 06:02 UTC

          Comment on this article