#### 1. INTRODUCTION

The problem of the relation between $\mathcal{P}$-class problems polynomially solvable by a deterministic computer and $\mathcal{N}P$-class problems polynomially solvable by a non-deterministic computer is considered as one of basic unsolved millennium problems.

Foundation of $\mathcal{N}P$-complete problems is laid by S. A. Cook [1]. He introduced the concepts of $\mathcal{N}P$-class problems, polynomial reducibility, and $\mathcal{N}P$-complete problem to which a problem of $\mathcal{N}P$ class is polynomially reducible. At present, $\mathcal{N}P$-completeness for many of $\mathcal{N}P$-class problems is proved. In particular, the “Hamiltonian cycle” problem is $\mathcal{N}P$-complete [2, 3].

Nowadays a topical question is whether $\mathcal{N}P$-complete problems are intractable. A proof of the possibility to solve an $\mathcal{N}P$-complete problem with a polynomial algorithm is the proof of $\mathcal{P}$ and $\mathcal{N}P$ equivalence.

In this paper, a polynomial algorithm for the $\mathcal{N}P$-complete “Hamiltonian circuit” problem is presented which means that the polynomial solvability for $\mathcal{N}P$-complete problems is proved.

#### 2. “HAMILTONIAN CIRCUIT” PROBLEM

Statement of the “Hamiltonian circuit” problem is given as [3, c. 35–37]:

INSTANCE: The simple graph

*G*= (*V*,*E*) is given.QUESTION: Is it true that the graph

*G*contains hamiltonian circuit, i.e. a sequence of vertices 〈*v*_{1},*v*_{2}, …,*v*〉 of the graph_{n}*G*vertices such that*n*= |*V*(*G*) |, {*v*,_{i}*v*_{i+1}} ∈*E*(*G*) for all*i*: 0 ≤*i*≤*n*− 2 and {*v*_{n−1},*v*_{0}} ∈*E*(*G*).

In this paper we present a polynomial algorithm for the “Hamiltonian circuit” problem that is a proof of the polynomial solvability for $\mathcal{N}P$-complete problems.

#### 3. LOCATION OF VERTICES OF CYCLE *C* ON GRAPH *G*

Let *C* be a simple cycle, *V*(*C*) = {*c*_{0}, *c*_{1}, …, *c*_{n−1}} be a set of vertices, and *E*(*C*) = {{*c _{i}*,

*c*

_{(i+1)%n}}:

*i*= 0, 1, …,

*n*− 1} be a set of edges where

*a*%

*b*is modulo of integers

*a*and

*b*.

The problem of determining the existence of Hamiltonian circuit in the graph *G* is equivalent the problem of recognizing the existence of bijection:

#### 4. STATEMENT IN THE FORM OF BOOLEAN PROGRAMMING PROBLEM

Let us consider a Boolean optimization problem:

*φ*:

*V*(

*C*) →

*V*(

*G*) be a map. Let us define

*x*as:

*(·) is the characteristic function of the set*

_{X}*X*. Constraints (4.2) represent the requirement that all vertices

*c*∈

_{i}*V*(

*C*) get their assignments. Constraints (4.3) represent the requirement that for each vertex

*v*∈

*V*(

*G*) is assigned to a certain

*c*∈

_{i}*V*(

*C*). Value of the loss function

*F*(

*x*) is equal to number of edges belonging to $E(\overline{G})$ in the image

*φ*(

*C*) of the placed cycle

*C*. If graph

*G*has a Hamiltonian circuit and

*x** is the optimal solution of (4.1), then

*F*(

*x**) = 0, otherwise

*F*(

*x**) ≥ 1.

#### 5. RELAXATION OF THE INTEGRALITY CONDITIONS

Algorithmic analysis of a combinatorial problem is significantly simplified after the consideration of the corresponding continuous statement. The quadratic assignment problem:

that differs from problem (4.1) by the replacement of the discreet set*D*into continuous set $\tilde{D}={D}_{1}\cap {D}_{2}\cap {[0,1]}^{{n}^{2}}$ is named a

*relaxed*problem. The feasible region $\tilde{D}$ of the relaxed problem is defined by constraints (4.2), (4.3), and

*x*≥ 0, i.e. $\tilde{D}$ is the matching polytope of the complete bipartite graph

*K*. Each vertex of $\tilde{D}$ corresponds to the Hamiltonian circuit in the graph

_{nn}*K*, and the value of the objective function

_{n}*F*(·) at any vertex of the polytope $\tilde{D}$ is equal to the number of edges belonging to $E(\overline{G})$ for the corresponding Hamiltonian circuit.

Thus, if *G* has *f* Hamiltonian circuit then according to the non-negativity of *F*(*x*) for *x* ∈ *D* the optimal value of the relaxed problem is:

*G*does not have a Hamiltonian circuit then: where $\text{vertex}(\tilde{D})$ is the vertex set of the polytope $\tilde{D}$.

Since any point of the polytope is a convex combination of its vertices, for non-Hamiltonian graphs we have:

*F*(·) having the matrix with non-negative items yields the first inequality of this chain. The second inequality is the result of inequality (5.2). Finally, the third inequality follows from:

**Proposition 5.1.** Let $\tilde{F}$ be the optimal value of relaxed problem (5.1).

If $\tilde{F}=0$, then

*G*= (*V*,*E*) has a Hamiltonian circuit.If $\tilde{F}\ge 1/n!$, then

*G*= (*V*,*E*) does not have a Hamiltonian circuit.

**Corollary 5.2.** It is sufficient to calculate the optimal value $\tilde{F}$ with an absolute error no more than 1/(3n!). No more than (2 + *n* log_{2} *n*) bits are required for the representation of $\tilde{F}$.

Relaxed problem (5.1) keeps intractability because it has many local minimums.

#### 6. DUAL PROBLEM

Lagrangian function of problem (4.1) is of the form:

*λ*) is convex upwards and upper bounded by the optimal value of the problem (4.1) that exists and is finite [5]. The problem of finding the maximal value of the dual function Λ(

*λ*) can be solved by the application of known convex non-smooth optimization methods [6]. Let us consider the possibility to apply the ellipsoid method [7] for solving the problem:

#### 7. APPLICATION OF THE ELLIPSOID METHOD

The ellipsoid method scheme from [7] is represented at Figure 1.

This method allows finding an *ε*-solution of the problem

satisfying the conditions

*B*

_{2}(

*λ*,

*ρ*) is the Euclidian ball with the center

*λ*and the radius

*ρ*by applying iterations.

For current Lagrange multipliers *λ*^{k} the *k*-th iteration of the ellipsoid algorithm comprises computing the value of Λ(*λ*^{k}), the separate vector *g*, the Lagrange multipliers *λ*^{k+1}, and the matrix *H*_{k+1}.

So to construct an algorithm for calculating the maximum value of Λ(*λ*) by the ellipsoid method it is sufficient to determine

the region

*S*∋ arg max_{λ}_{≥0}Λ(*λ*) and the ball*B*(*λ*^{0},*R*) ⊃*S*;the Lipshitz constant

*L*: | Λ(*λ*^{1}) − Λ(*λ*^{2}) | ≤*L*· | |*λ*^{1}−*λ*^{2}| |_{2};the algorithm for calculating the value Λ(

*λ*) for all*λ*∈*B*(*λ*^{0},*R*);the algorithm for calculating the subgradient ▽ Λ(

*λ*);the algorithm for calculating the vector

*g*of the hyperplane separating set*S*and the point*μ*∉*S*.

#### 8. LOCALIZATION OF THE OPTIMAL LAGRANGE MULTIPLIERS

Necessary conditions of the extreme of *L*(*x*, *λ*, *ν*) are

**Proposition 8.1.** The feasible solution set of system (8.1)–(8.6) contains a solution (x, λ, ν): λ ≥ 0, ν ≥ 0.

*Proof*. It is following from (8.1)–(8.6) that

*λ*= {

*λ*}

_{v}

_{v}_{∈}

*$\nu ={\left\{{\nu}_{i}\right\}}_{i=0}^{n-1}$ is satisfying to (8.1)–(8.3) then $\tilde{\lambda}={\{{\lambda}_{v}-m\}}_{v\in V}$ and $\tilde{\nu}={\{{\nu}_{i}+m\}}_{i=0}^{n-1}$ then $\tilde{\lambda}\ge 0$, $\tilde{\nu}\ge 0$ is satisfying (8.1)–(8.3) too.*

_{V}Let as introduce variables

**Proposition 8.2.**

*Proof*. The summation of equations (8.1)–(8.3) over *i* = 0, 1, …, *n* − 1 results is

*ρ*(

*v*) is the number of edges in the graph

*G*that are incident to vertex

*v*∈

*V*.

The summation of equations (8.9) over all *v* ∈ *V* results is

It is following from proposition 8.1 that *ν* ≥ 0 and *λ* ≥ 0 exist therefore we have

**Proposition 8.3.** *Let*

*Proof*. It is easy to check that *λ*^{0} is a projection of the origin on the hyperplane defined by the equation $\sum _{v\in V}{\lambda}_{v}}=M$, *R* = | |*λ*^{0}| |_{2} and | |*λ*^{0} − *λ* | | ≤ *R* for any vertex *λ* of the simplex *S*. Therefore *S* ⊂ *B*_{2}(*λ*^{0}, *R*).

By symmetry, the ball with the maximal radius *r* inscribed in the simplex *S* has center $\widehat{\lambda}={\left\{{\widehat{\lambda}}_{v}=r\right\}}_{v\in V}$ at that $r={\Vert {\lambda}^{0}-\widehat{\lambda}\Vert}_{2}$. Therefore $r=M/(n+\sqrt{n})$.

#### 9. LIPSHITZ CONSTANT

Let *λ*^{1}, *λ*^{2} ≥ 0 be. Let us assume Λ(*λ*^{1}) ≤ Λ(*λ*^{2}),

**Proposition 9.1.** Let $L=(n+1)\sqrt{n}$ be, then

#### 10. PROPERTIES OF THE OPTIMAL VALUE OF THE DUAL PROBLEM

Let us estimate possible values of Λ(*λ*) to find a reasonable calculation error.

**Proposition 10.1.**

*Proof*. Let

It is following from the convexity of Λ(*λ*), the boundedness of *S*, and the necessary optimality conditions that exist *λ*^{o} ∈ *S* and *x*(*λ*^{o}) satisfying the condition

*x*(

*λ*

^{o}) is a convex combination of points of set ${\left\{0,1\right\}}^{{n}^{2}}\cap {D}_{1}$ then taking into account (10.2) we have $x({\lambda}^{o})\in \tilde{D}$. Therefore

The corollary of propositions (5.1) and (10.1) is

**Proposition 10.2.** Let Λ* = max_{λ∈S}Λ(*λ*) be the optimal value of dual problem (7.1).

If Λ* = 0, then G = (V, E) has a Hamiltonian circuit.

If Λ* ≥ 1/(*n*!), then G = (V, E) does not have a Hamiltonian circuit.

It is follow from proposition 5.1 that it is sufficient to find an approximate Lagrange multipliers vector *λ**: Λ* − Λ(*λ**) ≤ *ε* = 1/(*n*!). Indeed, this inequality implies Λ* ≤ Λ(*λ**) + *ε*, which subsequently implies ${\Lambda}^{*}\le \lfloor \Lambda ({\lambda}^{*})+\epsilon \rfloor $. Since Λ(*λ**) ≤ Λ* then ${\Lambda}^{*}=\lfloor \Lambda ({\lambda}^{*})+\epsilon \rfloor $.

**Proposition 10.3.** If the error of the dual function Λ(*λ*) calculation is no more than *ε* = 1/(*n*!) then the ellipsoid algorithm solves a “Hamiltonian circuit” problem correctly.

#### 11. NUMBER OF ITERATIONS OF THE ELLIPSOID ALGORITHM

The variables of expression (7.4) are equal

Here, the last inequality is true for *n* ≥ 10.

#### 12. CALCULATION OF Λ(*λ*)

It is follow from (6.2) that it is sufficient to suggest the effective algorithm for solving the problem

*λ*). Problem (12.1) is a special case of the polynomially solvable Weber problem on a tree network [8]. Let us give a sketch of the chain adaptation of the algorithm from [9] for the purpose of presentation completeness.

Let us locate the vertex *c*_{0} ∈ *V*(*C*) at the vertex *v*_{0} ∈ *V*(*G*). Such fixation cuts down the number of locations and does not change the optimal value of the problem.

Let us introduce a state transition digraph $\mathcal{G}$ with the node set

*v*

_{0}, 0) − (

*v*

_{0},

*n*) path problem when the weights of the nodes $(v,i)\in V(\mathcal{G})$ are equal to

*λ*, and the weights of the arcs $\left((u,i),\text{\hspace{0.17em}}(v,i+1)\right)\in A(\mathcal{G})$ are (1 −

_{v}*χ*

_{E(G)}{

*u*,

*v*}). This problem may be solved by any common shortest path algorithms. The number of nodes $|V(\mathcal{G})|$ is

*n*

^{2}and the in-degree of all nodes is no more than

*n*. Therefore algebraic computation complexity of finding the optimal solution

*λ*) is no more than

*O*(

*n*

^{3}).

#### 13. PRECISION OF LAGRANGE MULTIPLIERS

The estimation of algebraic computational complexity expresses the number of operations with operands for the representation of which only one register is required. But for fixed point number representation with an absolute error no more than *δ* the sufficient number of *r*-digital registers must be no less than $\lceil \left|{\mathrm{log}}_{2}\delta \right|/r\rceil $. The computational bit complexity of the algorithm for problem (12.1) with these data is equal to *O*(*n*^{3}|log_{2}*δ* |).

The algorithm for problem (12.1) contains only “add” and “compare” operations with data only. Using the fixed point format makes all computations accurate. If the absolute errors of the data is no more than *δ* then the absolute error of the calculated value Λ(*λ _{v}*) is no more than

*ε*=

*n*·

*δ*as any intermediate result are sum of no more than

*n*approximate summands.

The accessible boundary of the error of Λ(*λ*) equal to *ε* = 1/(3·*n*!) in accordance to proposition (10.2). Therefore the error *δ* = 1/(3*n*·*n*!) for all *λ _{v}*,

*v*∈

*V*is sufficient and the following assertion is valid.

**Proposition 13.1.** The computational complexity of calculating Λ(λ) is no more than O(n^{4}log_{2}n).

#### 14. CALCULATION OF *g*_{k}

The case of *λ*^{k} ∉ *S* is possible when ${\lambda}^{k}\overline{)\ge}0$ or $\sum _{v\in V}{\lambda}_{v}^{k}}>M$. In the first case

*g*= {

_{k}*g*= −1}

_{kv}

_{v}_{∈}

*.*

_{V}Hence, the computational complexity of calculating *g _{k}* is no more than

*O*(

*n*log

_{2}

*n*) when

*λ*

^{k}∉

*S*.

If *λ*^{k} ∈ *S* then *g _{k}* = ▽ Λ(

*λ*). It follows from (6.2) for dual function Λ(

*λ*) that:

Therefore the computational complexity of finding ▽ Λ is no more than *O*(*n*) if the solution *x*(*λ*) is known.

#### 15. ELLIPSOID METHOD ITERATION COMPLEXITY

As it follow from the ellipsoid method description (Figure 1), the *k*-th iteration requires the calculation of the matrix *H*_{k+1} of the quadratic form for defining ellipse and Lagrange multipliers *λ*^{k+1} for the next iteration. The algebraic computational complexity of this procedure is equal to *O*(*n*^{2}).

The effectiveness of the ellipsoid method when of the Lagrange multipliers *λ*^{k} and items of the matrix *H*^{k} are fixed point numbers with the fractional part length equal to *p* = 5*N* = *O*(*n*^{3} log_{2} *n*) bits is proved [7, p. 173–176]. Therefore computational complexity of finding matrix *H*^{k} and vector *λ*^{k} is no more than *O*(*n*^{2}*N*) = *O*(*n*^{5} log_{2} *n*).

Hence, one iteration requires:

*O*(*n*^{4}log_{2}*n*) bit operations to solve(12.1);*O*(*n*log_{2}*n*) bit operations to calculate*g*;*O*(*n*^{5}log_{2}*n*) bit operations to find the matrix*H*^{k+1}and vector*λ*^{k+1}.

The requirements herein before explain that the computational bit complexity of an ellipsoid algorithm iteration is no more than *O*(*n*^{5} log_{2} *n*). It is important to point out that arbitrary-precision arithmetic is required.

#### 16. POLYNOMIAL SOLVABILITY OF $\mathcal{N}P$-CLASS PROBLEMS

Since the ellipsoid method performs *N* = *O*(*n*^{3} log_{2} *n*) iterations, we have proved:

**Theorem 16.1.** The computational complexity of a “Hamiltonian circuit” problem for graph G = (V, E), |V| = *n* is no more than $O\left({n}^{8}{\mathrm{log}}_{2}^{2}n\right)$.

The existence of a polynomial algorithm for a “Hamiltonian circuit” problem and $\mathcal{N}P$-completeness of this problem prove the polynomial solvability for all $\mathcal{N}P$-complete problems [1, 3]:

**Theorem 16.2.** $\mathcal{P}$ = $\mathcal{N}P$.

#### 17. CONCLUSION

The problem of recognizing the existence of a Hamiltonian circuit in graph is solvable in polynomial time, and consequently the polynomial solvability of $\mathcal{N}P$-complete problems is stated. Note there is no the contradiction to Mihalis Yannakakis results [6].