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

# Polynomial solvability of NP-complete problems

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(n8log22n), where n is the cardinality of the observed graph vertex set. Thus, the polynomial solvability for NP-complete problems is proved.

### Most cited references1

• Record: found

### Expressing combinatorial optimization problems by Linear Programs

(1991)
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

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
###### Categories
Original article

Computer science

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