For Publishers
DiscoveryMetadataPeer reviewHostingPublishing
For Researchers
JoinPublishReviewCollect
Register
Blog
About
Search
Advanced search

2,182
views
1
references
 Top references
0
cited by
 Most cited
    
0 reviews
 Review
4
comments
 Comment
0
recommends
+1 Recommend
1 collections
    33
    shares
      197
      similar
       All similar
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Polynomial solvability of NP-complete problems

      Read this article at

      ScienceOpen
      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

           Mihalis Yannakakis (1991)
          Article 0 comments Cited 119 times – based on 0 reviews     Review now
            Bookmark
            All references

            Author and article information

            Contributors
            Anatoly Panyukov: (View ORCID Profile)
            Journal
            Journal ID (publisher-id): SOR-COMPSCI
            Title: ScienceOpen Research
            Publisher: ScienceOpen
            ISSN (Electronic): 2199-1006
            Publication date: 16 December 2014
            Volume: 0 (ID: c0597241-52c2-47a7-8af0-dd09bbb57888 )
            Issue: 0
            Pages: 1-6
            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
            Article
            Publisher ID: 2207:XE
            DOI: 10.14293/S2199-1006.1.SOR-COMPSCI.AB0DLX.v1
            Copyright statement: © 2014 A. Panyukov.
            License:

            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
            Product
            Categories
            Subject: Original article

            Data availability:

            ScienceOpen disciplines: Computer science

            Keywords: Algorithm. Computational complexity. Hamiltonian cycle. Graph. NP-completeness

            Comments

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