Polynomial solvability of NP-complete problems

Abstract

A polynomial algorithm for solving the “Hamiltonian circuit” problem is presented in the paper. Computational complexity of the algorithm is equal to $O\left(n^8{\log }_2^{2}n\right)$, where n is the cardinality of the observed graph vertex set. Thus, the polynomial solvability for $\mathcal{N}P$-complete problems is proved.

Main article text

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₁, v₂, …, v_n〉 of the graph 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₀} ∈ E(G).

There have been unsuccessful attempts to solve the traveling salesman problem by a symmetric linear program. Mihalis Yannakakis closed the discussion with his paper [4] having proved that expressing the traveling salesman problem by a symmetric linear program requires exponential size.

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₀, c₁, …, 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:

$$\phi :V(C)\leftrightarrow V(G):\{\phi (c_i),\phi (c_{(i+1)\%n})\}\in E(G).$$

4. STATEMENT IN THE FORM OF BOOLEAN PROGRAMMING PROBLEM

Let us consider a Boolean optimization problem:

(4.1) $$F(x)={\displaystyle \sum _{i=0}^{n-1}\left({\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right)}\to \underset{x\in D}{\text{min}},$$

$\overline{E}(G)=V^2\setminus E(G)$, $D=D_1\cap D_2\cap {\left\{0,1\right\}}^{n^2}$

(4.2)$$D_1=\left\{x:{\displaystyle \sum _{v\in V(G)}{x}_v^i=1,i=0,1,2,\dots ,n-1}\right\}$$

(4.3) $$D_2=\left\{x:{\displaystyle \sum _{i=0}^{n-1}{x}_v^i=1,v\in V}\right\}.$$

Let φ: V(C) → V (G) be a map. Let us define x as:

(4.4) $$(\forall i=0,1,2,\dots ,n-1,v\in V(G))\left(x_v^i={\chi }_{\left\{v\right\}}(\phi (c_i))\right)$$

where χ_X(·) is the characteristic function of the set 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:

(5.1) $$F(x)\to \underset{x\in \tilde{D}}{\text{min}}$$

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_nn. Each vertex of $\tilde{D}$ corresponds to the Hamiltonian circuit in the graph K_n, and the value of the objective function 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:

$$\tilde{F}=\min \{F(x):x\in \tilde{D}\}=0.$$

But if G does not have a Hamiltonian circuit then:

(5.2) $$\tilde{F}=\min \{F(x):x\in \text{vertex}(\tilde{D})\}\ge 1$$

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:

$$\begin{array}{l}\tilde{F}=\min \{F(x):x\in \tilde{D}\}=\\ \min \left\{F\left({\displaystyle \sum _{x\in \text{ vertex}(\tilde{D})}x\cdot \alpha (x)}\right):{\displaystyle \sum _{x\in \text{vertex}(\tilde{D})}\alpha (x)=1,\alpha \ge 0}\right\}\ge \\ \min \left\{{\displaystyle \sum _{x\in \text{ vertex}(\tilde{D})}F}\left(x\right)\cdot {\alpha }^2(x):{\displaystyle \sum _{x\in \text{vertex}(\tilde{D})}\alpha (x)=1,\alpha \ge 0}\right\}\ge \\ \min \left\{{\displaystyle \sum _{x\in \text{vertex}(\tilde{D})}{\alpha }^2}(x):{\displaystyle \sum _{x\in \text{vertex}(\tilde{D})}\alpha (x)=1,\alpha \ge 0}\right\}\ge \frac{1}{n!}.\end{array}$$

The non-zero quadratic form 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:

$$\begin{array}{l}\arg \min \left\{{\displaystyle \sum _{x\in \text{vertex}(\tilde{D})}{\alpha }^2(x)}:{\displaystyle \sum _{x\in \text{vertex}(\tilde{D})}\alpha (x)=1,\alpha \ge 0}\right\}=\\ \left\{\alpha (x)=\frac{1}{|\text{vertex}(\tilde{D})|}=\frac{1}{n!}:x\in \text{vertex}(\tilde{D})\right\}.\end{array}$$

The foregoing proves following assertion.

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

(6.1) $$\begin{array}{l}L(x,\lambda ,\nu )={\displaystyle \sum _{i=0}^{n-1}\left({\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right)}+\\ {\displaystyle \sum _{v\in V}\left[{\lambda }_v\left(1-{\displaystyle \sum _{i=0}^{n-1}{x}_v^i}\right)\right]}+{\displaystyle \sum _{i=0}^{n-1}\left[{\nu }_i\left(1-{\displaystyle \sum _{v\in V}{x}_v^i}\right)\right]}.\end{array}$$

Let us make use of Lagrangian relaxations for constraints (4.3) to find the optimal value of problem (4.1) In this case the dual function is:

(6.2) $$\begin{array}{l}\Lambda (\lambda )=\underset{x\in {\{0,1\}}^{n^2}\cap D_1}{\text{min}}L(x,\lambda ,\nu )=\\ \underset{x\in {[0,1]}^{n^2}\cap D_1}{\text{min}}{\displaystyle \sum _{i=0}^{n-1}\left[-{\displaystyle \sum _{v\in V}{\lambda }_v{x}_v^i+}{\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right]}+{\displaystyle \sum _{v\in V}{\lambda }_v}.\end{array}$$

Function Λ(λ) 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:

(6.3) $$\Lambda (\lambda )\to \underset{\lambda }{\text{max}}.$$

7. APPLICATION OF THE ELLIPSOID METHOD

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

Figure 1.

The ellipsoid method scheme.

This method allows finding an ε-solution of the problem

(7.1) $$\Lambda (\lambda )\to \underset{\lambda \in S}{\text{max}}$$

satisfying the conditions

(7.2) $$(\exists {\lambda }^0,\widehat{\lambda }\in S,R,r\in R)\left(B_2(\widehat{\lambda },R)\subseteq S\subseteq B_2({\lambda }^0,r)\right)\subseteq R^n,$$

(7.3) $$(\forall {\lambda }^1,{\lambda }^2\in B_2({\lambda }^0,R))\left(|\Lambda ({\lambda }^1)-\Lambda ({\lambda }^2)|\le L{\Vert {\lambda }^1-{\lambda }^2\Vert }_2\right),$$

where B₂(λ, ρ) is the Euclidian ball with the center λ and the radius ρ by applying

(7.4) $$N=2\cdot {(n+1)}^2\lceil \text{ln}\frac{L{R}^2}{r\epsilon }\rceil$$

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

1. the region S ∋ arg max_{λ ≥0}Λ(λ) and the ball B(λ⁰, R) ⊃ S;

2. the Lipshitz constant L: | Λ(λ¹) − Λ(λ²) | ≤ L· | |λ¹−λ²| |₂;

3. the algorithm for calculating the value Λ(λ) for all λ ∈ B(λ⁰, R);

4. the algorithm for calculating the subgradient ▽ Λ(λ);

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

(8.1) $$\left(\forall v\in V\right)\left(\frac{\partial L}{\partial x_v^0}={\displaystyle \sum _{u:\{v,u\}\in \overline{E}(G)}\left(x_u^1+x_u^{n-1}\right)}-{\lambda }_v-{\nu }_0=0\right),$$

(8.2) $$\begin{array}{l}\left(\forall v\in V,i=1,2,\dots ,n-2\right)\\ \left(\frac{\partial L}{\partial x_v^i}={\displaystyle \sum _{u:\{v,u\}\in \overline{E}(G)}\left(x_u^{i-1}+x_u^{i+1}\right)}-{\lambda }_v-{\nu }_i=0\right),\end{array}$$

(8.3) $$\left(\forall v\in V\right)\left(\frac{\partial L}{\partial x_v^{n-1}}={\displaystyle \sum _{u:\left\{u\right\}\in \overline{E}(G)}\left(x_u^{n-2}+x_u^0\right)}-{\lambda }_v-{\nu }_{n-1}=0\right).$$

(8.4) $$\left(\forall i=0,1,2,\dots ,n-2,n-1\right)\left({\displaystyle \sum _{v\in V}{x}_v^i=1}\right),$$

(8.5) $$\left(\forall v\in V\right)\left({\displaystyle \sum _{i=0}^{n-1}{x}_v^i=1}\right),$$

(8.6) $$\left(\forall i=0,1,2,\dots ,n-2,n-1;\forall v\in V\right)\left(x_v^i\ge 0\right).$$

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

(8.7) $$\begin{array}{l}\left(\forall v\in V,i=0,1,2,\dots ,n-2,n-1\right)\left(0\le {\lambda }_v+{\nu }_i\right)\Rightarrow \\ \left(\forall i=0,1,2,\dots ,n-2,n-1\right)\left(m=-\underset{v\in V}{\text{min}}{\lambda }_v\le {\nu }_i\right).\end{array}$$

But it is easy to see that if λ = {λ_v}_{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.

Let as introduce variables

$$M=\frac{4n^2-4|E(G)|}{n},S=\left\{{\left\{{\lambda }_v\right\}}_{v\in V}:0\le {\displaystyle \sum _{v\in V}{\lambda }_v\le M,\lambda \ge 0}\right\}$$

to reduce lengthy statements and improve their readability.

Proposition 8.2.

(8.8) $${\lambda }^{*}=\text{arg}\underset{\lambda }{\text{max}}\Lambda (\lambda )\in S.$$

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

(8.9) $$\begin{array}{l}\left(\forall v\in V\right)({\displaystyle \sum _{u:\left\{u\right\}\in \overline{E}(G)}\left(2{\displaystyle \sum _{i=0}^{n-1}{x}_u^i}\right)}-n{\lambda }_v-{\displaystyle \sum _{i=0}^{n-1}{\nu }_i}\\ =2n-2\rho (v)-n{\lambda }_v-{\displaystyle \sum _{i=0}^{n-1}{\nu }_i}=0),\end{array}$$

where ρ(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

(8.10) $$2n^2-4|E(G)|-n{\displaystyle \sum _{v\in V}{\lambda }_v}-n{\displaystyle \sum _{i=0}^{n-1}{\nu }_i}=0.$$

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

$$0\le {\displaystyle \sum _{v\in V}{\lambda }_v}\le \frac{4n^2-4|E(G)|}{n}=M.$$

Proposition 8.3. Let

$${\lambda }^0={\left\{{\lambda }_v^0=\frac{M}{n}\right\}}_{v\in V},R=\frac{M}{\sqrt{n}},\widehat{\lambda }={\left\{{\widehat{\lambda }}_v=\frac{M}{n+\sqrt{n}}\right\}}_{v\in V},r=\frac{M}{n+\sqrt{n}},$$

then $B_2(\widehat{\lambda },r)\subset S\subset B_2({\lambda }^0,R)$.

Proof. It is easy to check that λ⁰ is a projection of the origin on the hyperplane defined by the equation ${\displaystyle \sum _{v\in V}{\lambda }_v}=M$, R = | |λ⁰| |₂ and | |λ⁰ − λ | | ≤ R for any vertex λ of the simplex S. Therefore S ⊂ B₂(λ⁰, 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 λ¹, λ² ≥ 0 be. Let us assume Λ(λ¹) ≤ Λ(λ²),

$$\tilde{x}=\text{arg}\underset{x\in {[0,1]}^n\cap D_1}{\text{min}}{\displaystyle \sum _{i=0}^{n-1}\left[-{\displaystyle \sum _{v\in V}{\lambda }_v^1}{x}_v^i+{\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right]}.$$

Evidently, this assumption does not reduce generality. Therefore,

(9.1) $$\begin{array}{l}\left|\Lambda ({\lambda }^1)-\Lambda ({\lambda }^2)\right|=\\ |\underset{x\in {[0,1]}^n\cap D_1}{\text{min}}{\displaystyle \sum _{i=0}^{n-1}\left[-{\displaystyle \sum _{v\in V}{\lambda }_v^1}{\displaystyle \sum _{i=0}^{n-1}{x}_v^i}+{\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right]}+{\displaystyle \sum _{v\in V}{\lambda }_v^1}\\ -\underset{x\in {[0,1]}^n\cap D_1}{\text{min}}{\displaystyle \sum _{i=0}^{n-1}\left[-{\displaystyle \sum _{v\in V}{\lambda }_v^2}{\displaystyle \sum _{i=0}^{n-1}{x}_v^i}+{\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right]}-{\displaystyle \sum _{v\in V}{\lambda }_v^2}|\le \\ \left|-{\displaystyle \sum _{v\in V}{\lambda }_v^2}{\displaystyle \sum _{i=0}^{n-1}{\tilde{x}}_v^i}+{\displaystyle \sum _{v\in V}{\lambda }_v^1}{\displaystyle \sum _{i=0}^{n-1}{\tilde{x}}_v^i}\right|+\left|{\displaystyle \sum _{v\in V}{\lambda }_v^1}-{\displaystyle \sum _{v\in V}{\lambda }_v^2}\right|\le \\ (n+1){\displaystyle \sum _{v\in V}\left|{\lambda }_v^1-{\lambda }_v^2\right|}\le (n+1)\sqrt{n}{\Vert {\lambda }^1-{\lambda }^2\Vert }_2.\end{array}$$

Thus, it is proved

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

(9.2) $$(\forall {\lambda }^1,{\lambda }^2\ge 0)\left(|\Lambda ({\lambda }^1)-\Lambda ({\lambda }^2)|\le L{\Vert {\lambda }^1-{\lambda }^2\Vert }_2\right).$$

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.

$$\underset{\lambda \in S}{\text{max}}\Lambda (\lambda )\ge \underset{x\in \tilde{D}}{\text{min}}F(x).$$

Proof. Let

(10.1) $$x(\lambda )=\text{arg}\underset{x\in {\{0,1\}}^n\cap D_1}{\text{min}}{\displaystyle \sum _{i=0}^{n-1}\left[-{\displaystyle \sum _{v\in V}{\lambda }_v}{x}_v^i+{\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right]}.$$

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

(10.2) $$\nabla \Lambda ({\lambda }^o)={\left\{\nabla \Lambda {({\lambda }^o)}_v=1-{\displaystyle \sum _{i=1}^{n-1}x{({\lambda }^o)}_v^i}\right\}}_{v\in V}=0.$$

Since 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

$$\underset{x\in \tilde{D}}{\text{min}}F(x)\le F(x({\lambda }^o))=\Lambda ({\lambda }^o).$$

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

$$R=\frac{M}{\sqrt{n}},r=\frac{M}{n+\sqrt{n}},M=4n^2\left(1-\frac{|E(G)|}{n^2}\right),L=(n+1)\sqrt{n},\epsilon =1/(n!)$$

in accordance with assertions 8.2, 8.3, 9.1 and 10.3. Therefore we have an estimation

(11.1) $$\begin{array}{l}N=2\cdot {(n+1)}^2\lceil \text{ln}\frac{L{R}^2}{r\epsilon }\rceil =\\ 2\cdot {(n+1)}^2\lceil \text{ln}\left[4n\sqrt{n}(n+1)(n+\sqrt{n})\left(1-\frac{|E(G)|}{n^2}\right)\cdot (3n!)\right]\rceil <\\ 2{(n+1)}^2\lceil 25+5{\log }_{2}n+143\cdot n{\log }_{2}n\rceil .\end{array}$$

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

(12.1) $${\displaystyle \sum _{i=0}^{n-1}\left[-{\displaystyle \sum _{v\in V}{\lambda }_v}{x}_v^i+{\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i}{x}_u^{(i+1)\%n}\right]}\to \underset{x\in {\{0,1\}}^n\cap D_1}{\text{min}}.$$

that may calculate the value of Λ(λ). 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₀ ∈ V(C) at the vertex v₀ ∈ 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

(12.2) $$V(\mathcal{G})=\left\{(v_0,0),(v_0,n)\right\}{\displaystyle \cup \left[{\displaystyle \underset{u,v\in V(G)\setminus \left\{v_0\right\}}{\cup }\left(\left(V(G)\setminus \left\{v_0\right\}\right)\times \left\{1,2,\dots ,n-1\right\}\right)}\right]}$$

and the arc set

$$\begin{array}{l}A(\mathcal{G})=\left[{\displaystyle \underset{v\in V(G)\setminus \left\{v_0\right\}}{\cup }\left\{\left((v_0,0),(v,1)\right)\right\}}\right]\cup \\ \left[{\displaystyle \underset{i=1}{\overset{n-2}{\cup }}\left({\displaystyle \underset{u,v\in V(G)\setminus \left\{v_0\right\}}{\cup }\left\{\left((u,i),(v,i+1)\right)\right\}}\right)}\right]\cup \\ \left[{\displaystyle \underset{v\in V(G)\setminus \left\{v_0\right\}}{\cup }\left\{\left((v,n-1),(v_0,n)\right)\right\}}\right].\end{array}$$

Problem (12.1) in terms of digraph $\mathcal{G}$ is the minimum weight (v₀, 0) − (v₀, n) path problem when the weights of the nodes $(v,i)\in V(\mathcal{G})$ are equal to λ_v, and the weights of the arcs $\left((u,i),(v,i+1)\right)\in A(\mathcal{G})$ are (1 − χ_E(G){u, v}). This problem may be solved by any common shortest path algorithms. The number of nodes $|V(\mathcal{G})|$ is n² and the in-degree of all nodes is no more than n. Therefore algebraic computation complexity of finding the optimal solution

$$x(\lambda ))=\text{arg}\underset{x\in {[0,1]}^n\cap D_1}{\text{min}}{\displaystyle \sum _{i=0}^{n-1}\left[-{\displaystyle \sum _{v\in V}{\lambda }_v}{x}_v^i+{\displaystyle \sum _{v,u:\{v,u\}\in \overline{E}(G)}{x}_v^i{x}_u^{(i+1)\%n}}\right]}$$

and the calculation of Λ(λ) is no more than O(n³).

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|{\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³|log₂δ |).

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/(3n·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⁴log₂n).

14. CALCULATION OF g_k

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

$$g_k={\left\{g_{kv}=\{\begin{array}{ll}0,\hfill & {\lambda }_v\ge 0;\hfill \\ 1,\hfill & {\lambda }_v<0\hfill \end{array}\right\}}_{v\in V},$$

and in the second one g_k = {g_kv = −1}_{v∈ V}.

Hence, the computational complexity of calculating g_k is no more than O(n log₂ n) when λ^k ∉ S.

If λ^k ∈ S then g_k = ▽ Λ(λ). It follows from (6.2) for dual function Λ(λ) that:

$$\nabla \Lambda (\lambda )={\left\{{\lambda }_v=1-{\displaystyle \sum _{i=1}^{n-1}x{(\lambda )}_v^i}\right\}}_{v\in V}.$$

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²).

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 = 5N = O(n³ log₂ 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²N) = O(n⁵ log₂ n).

Hence, one iteration requires:

1. O(n⁴ log₂ n) bit operations to solve(12.1);

2. O(n log₂ n) bit operations to calculate g;

3. O(n⁵ log₂ 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⁵ log₂ 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³ log₂ 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{\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].

Acknowledgments

The author wishes to express his most sincere thanks to Anatoly V. Lakeev for valuable comments on this manuscript.

References

1. Cook SA. The complexity of theorem-proving procedures. In: , , , editors. Proceedings of 3-rd annual computation on theory of computing. New York (NY): Association of Computing Machinery; 1971. p. 151–8.

2. Karp RM. Reducibility among combinatorial problems. In: , , editors. Complexity of computer computation. New York (NY): Plenum Press; 1972. p. 85–103.

3. . . Computer and intractability: a guide for the theory of np-completeness. Murray Hill (NJ): Bell Laboratories; San Francisco (CA): W. H. Freeman and Company; 1979.

4. Yannakakis M. Expressing combinatorial optimization problems by linear programs. J Comp Syst Sci. 1991;43(3):441–66. [Cross Ref]

5. Minoux M. Programmation mathmatique: Thorie et algorithmes dunod (Mathematical Programming: Theory and Algorithms), Collection Technique et Scientifique des Tlcommunications, Bordas et C.N.E T. Paris: E.N.S.T; 1983, 1989. (in French)

6. Nesterov Y. Introductory lectures on convex optimization: a basic course. Amsterdam: Kluwer; 2010.

7. , , . The ellipsoid method and its consequences in combinatorial optimization. Combinatorica. 1981;1(2):169–97.

8. , . The optimal distributions of a tree in a finite set. Comput Math Math Phys. 1988;28:204–6.

9. , . Polynomial algorithms to finite weber problem for a tree network. J Comput App Math. 1991;35:291–6.

Competing Interests

The authors declare no competing interests.

Publishing Notes

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