Blog
About

1,907
views
0
recommends
+1 Recommend
1 collections
    17
    shares
    • Record: found
    • Abstract: found
    • Article: found
    Is Open Access

    Polynomial solvability of N P -complete problems

    Read this article at

    Bookmark
        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.

        Abstract

        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

          Bookmark

          Author and article information

          Affiliations
          [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
          Contributors
          (View ORCID Profile)
          Journal
          SOR-COMPSCI
          ScienceOpen Research
          ScienceOpen
          2199-1006
          16 December 2014
          : 0 (ID: c0597241-52c2-47a7-8af0-dd09bbb57888 )
          : 0
          : 1-6
          2207:XE
          10.14293/S2199-1006.1.SOR-COMPSCI.AB0DLX.v1
          © 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 .

          Counts
          Figures: 1, Tables: 0, References: 9, Pages: 6
          Product
          Categories
          Original article
          ScienceOpen disciplines:
          Keywords:

          Comments

          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
          +1
          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
          +1
          It necessary all symbols $C$ to replace by symbol $F$ in the formula following formula (5.2).
          2015-01-30 16:25 UTC
          +1
          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
          +1

          Comment on this article