+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 ( n 8 log 2 2 n ) , where n is the cardinality of the observed graph vertex set. Thus, the polynomial solvability for N P -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

            (View ORCID Profile)
            ScienceOpen Research
            16 December 2014
            : 0 (ID: c0597241-52c2-47a7-8af0-dd09bbb57888 )
            : 0
            : 1-6
            [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@ 123456gmail.com
            © 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 www.scienceopen.com .

            Page count
            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