On Polynomial Time Absolute Approximation-bounded Solution of TSP
and NP Complete Problems
Wenhong Tiana

arXiv:1605.06183v2 [] 18 Dec 2016

a School of Information and Software Engineering,
University of Electronic Science and Technology of China (UESTC)

Abstract
The question of whether all problems in NP class are also in P class is generally considered one of the most
important open questions in mathematics and theoretical computer science as it has far-reaching consequences to other problems in mathematics, computer science, biology, philosophy and cryptography. There
are intensive research on proving ‘NP not equal to P’ and ‘NP equals to P’. However, none of the ‘proved’
results is commonly accepted by the research community up to date. In this paper, motived by approximability of traveling salesman problem (TSP) in polynomial time, we provide a polynomial time absolute
approximation-bounded solution of TSP in Euclidean space. It may shine light on solving other NP complete
problems in similar way.
Keywords: NP problems, P Problems, P versus NP, TSP, Polynomial Time Absolute Approximation
Bounded Solutions

1. Introduction
P versus NP problem is one of seven Millennium Prize Problems in mathematics that were stated by
the Clay Mathematics Institute [1] in 2000. As of Dec 2016, six of the problems remain unsolved. The
official statement of P versus NP problem was given by Stephen Cook [2]. In computational complexity
theory, Karp’s 21 NP-complete problems are a set of computational problems which are NP-complete. In his
1972 paper [9], Richard Karp used Stephen Cook’s 1971 theorem that the Boolean satisfiability problem is
NP-complete (also called the Cook-Levin theorem) to show that there is a polynomial time many-one reduction from the Boolean satisfiability problem (BSP) to each of 21 combinatorial problems, thereby showing
that they are all NP-complete. This was one of the first demonstrations that many natural computational
problems occurring throughout computer science are computationally intractable, and it drove interest in
the study of NP-completeness and the P versus NP problem.
Simply speaking, P problems mean that the class of problems can be solved exactly in polynomial time
while NP (non-deterministic polynomial) problem stands for a class of problems which can not be solved in
polynomial time. Intuitively, NP problem is the set of all decision problems for which the instances where the
answer is “yes” have efficiently verifiable proofs of the fact that the answer is indeed “yes”. More precisely,
these proofs have to be verifiable in polynomial time by a deterministic Turing machine. In an equivalent
formal definition, NP problems is the set of decision problems where the “yes”-instances can be accepted in
polynomial time by a non-deterministic Turing machine [18]. NP problems has far-reaching consequences to
other problems in mathematics, biology, philosophy and cryptography.
The complexity class P is contained in NP, and NP contains many important problems. The hardest
of which are NP-complete problems, whose solutions are sufficient to deal with any other NP problems in
polynomial time. The most important open question in complexity theory, is the P versus NP problem which
asks whether polynomial time algorithms actually exist for NP-complete problems and all NP problems. The
Preprint submitted to Elsevier

December 20, 2016

important thing is that Karp showed that if any of them have efficient polynomial time algorithms, then they
all do. Many of these problems arise from real-world optimization problems including Sub Set Sum Problem (SSP), Traveling Salesman Problem (TSP), Bin Packing Problem (BPP), Hamiltonian Cycle Problem
(HCP), and Chromatic Number Problem (CNP) etc.. Researchers later extend Karp’s techniques to show
hundreds, if not thousands of natural problems, are NP-complete.
It is widely believed that NP!=P in 2002 [4]. In 2012, 10 years later, the same poll was repeated [5].
The number of researchers who answered was 126 (83%) believed the answer to be no, 12 (9%) believed
the answer is yes, 5 (3%) believed the question may be independent of the currently accepted axioms and
therefore is impossible to prove or disprove, 8 (5%) said either don’t know or don’t care or don’t want the
answer to be yes nor the problem to be resolved. On the Web site [18] , Prof. Gerhard Woeginger provides the unofficial archivist of about 116 claims for the NP vs P problem from 1986 to April 2016, among
them, 49 (42%) believed the answer to be no, 62 (53%) believed the answer is yes, the other 5 (5%) think
Undecidable, or Unprovable or Unknow. About nine of papers in the list ‘established’ NP=P by designing algorithms for variants of the TSP, though none of them is commonly accepted yet by the research community.
As for approximation of TSP, Christofides [Christofides,1976] provided an absolute 1.5-approximation
algorithm. Arora [Arora, 1998] proposed an asymptotical (1+1/c)-approximation algorithm, but its computational complexity is of O(n(logn)O(c) ) where (logn)O(c) can be huge since c can be a few tens or larger,
therefore it is not a practical algorithm but asymptotical bounded approximation (this is confirmed by Prof.
Arora through email). Tian et al. [Tian et al., 2016] introduced TGB algorithm with absolute approximation
K−1
)-approximation where K is the number of iterations in TGB and α is the shape parameter
of (1+ 12 ( α+1
α+2 )
of Generalized Beta distribution (introduce in Section 3) and can be obtained once a TSP is given. In this
paper, we focus on absolute approximation but not asymptotical approximation. For convenience, we just
use approximation to represent absolute approximation.
In [Papadimitriou and Vempala, 2006], Papadimitriou and Vempala proved that, unless NP=P, there can be
no polynomial-time C-approximation algorithm for the metric TSP with C less than 220
219 , i.e., less than 0.45%.
In this paper, we aim to propose is a absolute bounded approximation algorithm for TSP in Euclidean space.
The remaining sections are organized as follows. TSP is discussed in Section 2. Approximation bounded
algorithm for TSP is proposed in Section 3. Our main results are provided in Section 4. Finally we conclude
in Section 5.
2. TSP Formulation in Euclidean Space
The TSP is one of most researched problems in combination optimization because of its importance in
both academic need and real world applications. For surveys of the TSP and its applications, the reader is
referred to [Cook, 2012] and references therein. We consider the n-node TSP defined in Euclidean space.
This can be represented on a complete graph G= (V, E) where V is the set of nodes and E is the set of
edges. The cost of an edge (u, v) is the Euclidean distance (cuv ) between u and v. Let the edge cost matrix
be C[cij ] which satisfies the triangle inequality.
Definition 1. Symmetric TSP (STSP) is TSP in Euclidean distance (called ESTSP) and the edge cost
matrix C is symmetric.
Definition 2. Asymmetric TSP (ATSP) is TSP in Euclidean distance (called EATSP) and the edge cost
matrix C is asymmetric.
Definition 3. 4STSP is a STSP whose edge costs are non-negative and satisfies the triangle inequality,
i.e., for any three distinct nodes (not necessary neighboring) (i, j, k), (cij +cjk ) ≥ cik . The STSP is also
called the metric TSP.
Definition 4. TSP tour. Given a graph G in 2-dimensional Euclidean distance and its distance matrix
C where cij denote the distance between node i and j (for both symmetric and asymmetric). A tour T with
|V | nodes has length

2

|V |−1

L=

X

cT (k),T (k+1)

(1)

k=0

In 1977, Papadimitriou [Papadimitriou,1977] firstly proved that the Euclidean TSP (ETSP) is NPcomplete by reduction of the Exact Cover Problem to the ETSP.
3. On the Approximability of Metric TSP
On the approximability of metric TSP, there is a well-known theorem as follow.
Papadimitriou-Vempala Theorem. In [Papadimitriou and Vempala,2006], Papadimitriou and Vempala
(let us call it Papadimitriou-Vempala Theorem) proved that, unless NP=P, there can be no polynomial-time
220
, i.e., less than 0.45%.
C-approximation algorithm for the metric TSP with C less than 219
Before continuing, the following two definitions are introduced:
Definition 5. maxTSP. The maximum tour length (B) is obtained using LKH where each edge cost (cij ) is
replaced by a very large value (M ) minus the original edge cost, i.e., (M -cij ). M can be set as the maximum
edge cost plus 1.
Definition 6. k-opt. is a local search with k-exchange neighborhoods and the most widely used heuristic
method for the TSP. k-opt is a tour improvement algorithm, where in each step k links of the current
tour are replaced by k links in such a way that a shorter tour is achieved (see [Helsgaun 2009] for detailed
introduction).
In the following, we propose an algorithm called ITGBC which can obtain approximation ratio less than 220
219
for metric TSP.
We firstly propose a Generalized Beta (GB) distribution [Tian et al., 2016]. The probability density
function (pdf) of GB is defined as
(x − A)α−1 (B − x)β−1
Beta(α, β)

f (x, α, β, A, B) =

(2)

where Beta(α, β) is the beta function
Z
Beta(α, β) =

1

tα−1 (1 − t)β−1 dt,

(3)

0

A and B is the lower bound and upper bound respectively, α > 0, β > 0. For TSP, A and B represents the
minimum and maximum tour length (maxTSP) respectively.
Some of the following results are introduced in [Tian et al, 2016], for completeness, we restate here and
introduce Iterative Truncated Generalized Beta distribution Based on Christofides Algorithm
(ITGBC) firstly. ITGBC algorithm performs in seven steps:
• (1). Finding the minimum spanning tree M ST of the input graph G representation of metric TSP;
• (2). Taking G restricted to vertices of odd degrees in M ST as the subgraph G∗ ; This graph has an
even number of nodes and is complete;
• (3). Finding a minimum weight matching M ∗ on G∗ ;
• (4). Uniting the edges of M ∗ with those of the M ST to create a graph H with all vertices having even
degrees;

3

• (5). Creating a Eulerian tour on H and reduce it to a feasible solution using the triangle inequality, a
short cut is a contraction of two edges (i, j) and (j, k) to a single edge (i, k);
• (6). Applying Christofides algorithm [Christofides,1976] to a ESTSP forms a truncated GB (TGB)
for the probability density function of optimal tour lengths, with expectation (average) value at most
1.5OPT-, where  is a very small value; Applying k-opt to the result of Christofides algorithm forms
another TGB for probability density function of optimal tour lengths;
• (7). Iteratively applying this approach, taking the expectation value of (K − 1)-th iteration as the
µK−1 −A
upper bound (bˆK = tB−A ) of the K-th iteration, we have the expectation value (denoted as µK
t )
after K iterations (K ≥ 2), which is proved in [Tian et al., 2016],
µK
t = A + (B − A)

B2 (0, bˆK , α + 1, β)
B2 (0, bˆK , α, β)

= A + (B − A)g(bˆK )
1 α + 1 K−1
≤ (1 + (
)
)A
2 α+2
Z t
B2 (0, t, α, β) =
xα−1 (1 − x)β−1 dt

(4)

(5)

0
K−1
)-approximation where K is the number of iterations
Theorem 1. ITGBC algorithm is (1+ 21 ( α+1
α+2 )
in ITGBC algorithm, α is the shape parameter of TGB and can be determined once ETSP instance is given.
The present author proved Theorem 1 in [Tian et al., 2016] , for completeness, we provide the proof in the
following.

1
2
3

K

A

1.5A-ε 1.5A

B

Figure 1: The process in ITGBC algorithm

Proof. Applying k-opt to the result obtained by Christofide algorithm as shown in Fig.1. The TGB in this
case is truncated from above. Denote the first truncation by Christofides’ algorithm as the first truncation
4

(K=1). The probability density function of the second TGB is given by
(x − A)α−1 (B − x)β−1
ft2 (x, α, β, A, B, a2 , b2 ) = R b2
(x − A)α−1 (B − x)β−1
a2

(6)

In this case, a2 =A, b2 =1.5A because the distribution is based on the result after applying Christofides algox−A
A−A
0.5A
rithm which assures the upper bound is at most 1.5A, see Fig.1. Setting x̂= B−A
, aˆ2 = B−A
=0, bˆ2 = 1.5A−A
B−A = B−A ,
we have
Z b2
C0 =
(x − A)α−1 (B − x)β−1 dx
a2
bˆ2

Z
=

((B − A)x̂)α−1 ((B − A)(1 − x̂)β−1 dx

0

= (B − A)α+β−1 B2 (0, bˆ2 , α, β)
where
Z

(7)

t

xα−1 (1 − x)β−1 dt

B2 (0, t, α, β) =

(8)

0

By the definition of the expectation or mean value (denoted as µ2t ) for ft2 (x, α, β, A, B, a2 , b2 ), we have
Z b2
µ2t − A =
(x − A)ft2 (x, α, β, A, B, a2 , b2 )dx
a2

R b2
=
=

a2

(x − A)α (B − x)β−1 dx
C0

(B − A)

α+β

= (B − A)
=> µ2t = A + (B − A)

B2 (0, bˆ2 , α + 1, β)
C0
B2 (0, bˆ2 , α + 1, β)
B2 (0, bˆ2 , α, β)
B2 (0, bˆ2 , α + 1, β)

(9)

B2 (0, bˆ2 , α, β)
µK−1 −A

Taking the expectation value of (K − 1)-th iteration as the upper bound (bˆK = tB−A ) of the K-th
iteration, we apply this approach iteratively and have the expectation value after K iterations (K ≥ 2),
denoted as µK
t ,
µK
t = A + (B − A)

B2 (0, bˆK , α + 1, β)
B2 (0, bˆK , α, β)

= A + (B − A)g(bˆK )
Notice that the expectation value of the (K-1)-iteration is taken as the upper bound (bˆK =
is OPT and B is the maxTSP) of the K-iteration, as shown in Fig.1. Setting
g(bˆK ) =

B2 (0, bˆK , α + 1, β)
B2 (0, bˆK , α, β)

µK−1
−A
t
B−A

here A

(10)

The exact expression of g(bˆK ) can be stated in a hypergeometric series, and
α
bˆK
ˆ
B2 (0, bK , α, β) =
F (α, 1 − β, α + 1, bˆK )
α

5

(11)

and F (a, b, c, x)
a(a + 1)b(b + 1) 2
ab
x+
x
c
c(c + 1)2!
a(a + 1)(a + 2)b(b + 1)(b + 2) 3
+
x + ...
c(c + 1)(c + 2)3!
=1+

(12)

In all cases, we have α >1, β >1, bˆK ∈ (0, 1) as shown in [Tian et al., 2016], therefore F (a, b, c, x) is an
monotonic decreasing function. We have
α+1
u2t = A + (B − A)g(bˆ2 ) ≤ A + 0.5A
α+2

(13)

continue this for g(bˆ3 ), u3t , g(bˆ4 ), u4t ,..., so forth, we have
0.5A α + 1 K−1
bˆK ≤
(
)
B−A α+2

(14)

and
B2 (0, bˆK , α + 1, β)
g(bˆK ) =
B2 (0, bˆK , α, β)
α+1 ˆ
≤
bK
α+2
K−1
0.5A( α+1
α+2 )
=
,
B−A

(15)

Therefore
µK
t = A + (B − A)

B2 (0, bˆK , α + 1, β)
B2 (0, bˆK , α, β)

= A + (B − A)g(bˆK )
1 α + 1 K−1
≤ (1 + (
)
)A
2 α+2

(16)

This completes the proof.
Theorem 2. The
√ computational complexity of ITGBC algorithm is of
O(max(n3 , K(k 3 + k n))).
√
Proof: In [Helsgaun, 2009], a method with computational complexity of O(k 3 + k n) is introduced for
k-opt. Since ITGBC applies Christofides algorithm firstly which has computational complexity of O(n3 )
[Christofides,1976],
√ and then applies k-opt with K iterations in LKH which has computational complexity
of O(K(k 3 + k n)), the computational complexity of LKH is estimated to be√O(n2.2 ) [Helsgaun, 2009], so
altogether the computational complexity of ITGBC is of O(max(n3 , K(k 3 + k n))).

3.1. Our Main Results
Theorem 3. Metric TSP is one of NP complete problem [Papadimitriou, 1977], which can be solved by
220
ITGBC in polynomial time C-approximation with C less than 219
.

6

K−1
Proof. From Theorem 1, it can been seen the approximation ratio (1+ 12 ( α+1
) can be less than 220
α+2 )
219 .
Actually when the instance is given, the shape parameter α can be estimated easily as shown in [Tian et
al., 2016]. By fixing the approximation ratio to obtain the number of iterations in ITGBC, through a simple
log0.009
), the approximation ratio will be less than
numerical computation, we know when K > (1+ log(1−1/(α+2))
220
219 .

According to Papadimitriou-Vempala Theorem, this happens only when NP=P. This may imply NP=P.
4. Numerical Results
For implementation, ITGBC algorithm is based on Christofides’ algorithm and LKH source codes, so it
takes both advantages of them and provides approximation bounded results.
4.1. Polynomial Time Approximation-Bounded Solutions to ESTSP
The results in Table 1 are obtained from William J. Cook’s book [Cook, 2012], Chapter 1, where all
problems are solved to optimality by different tools except for 1000,000 city problem and 1,904,711 city
problem, for which optima are not known yet.
In Table 1, Nagata’s tour for 1000,00-city Mona Lisa tour is known to be at most 0.0003% longer than an
Table 1: TSP Records Variation By Years [Cook, 2012]

# Nodes

Year (Solved)

Description

Authors

48
64
80
120
318
532
666
1002
2392
3038
13509
15112
24978
85900
100000
1904711

1954
1971
1975
1977
1987
1987
1987
1987
1987
1992
1998
2001
2004
2006
2009*
2010*

USA cities
random nodes
random nodes
Germany cities
cities
USA cities
World cities
cities
cities
cities
USA cities
cities
Sweden cities
cities
Japan
World TSP Challenge

Dantzig et al.(by hand)
Micheal Held, Richard Karp
Panagiotis Miliotis
Martin Grotschel, Manfred Padberg
Manfred Padberg,Harlan Crowder
Martin Grotschel, Manfred Padberg
Martin Grotschel, Manfred Padberg
Martin Grotschel, Manfred Padberg
Martin Grotschel, Manfred Padberg
Concorde
Concorde
Concorde
Concorde
Concorde, LKH [Helsgaun,2009]
Yuchi Nagata
LKH [Helsgaun,2009]

optimal solution; The tour by LKH [Helsgaun,2009] for 1,904,711-city of length 7,515,790,345 meters was
known to be no more than 0.0476% longer than an optimal tour.
Definition 7. Concorde Algorithm [Concorde,2003]: Concorde is a computer code for the STSP
and some related network optimization problems. The code is written in the ANSI C programming language.
Concorde’s TSP solver has been used to obtain the optimal solutions to the full set of 110 TSPLIB instances,
the largest having 85,900 cities. Executable versions of Concorde with qsopt for Linux and Solaris are available [Concorde,2003]. Hans Mittelmann has created a NEOS Server (http:/neos-server.org) for Concorde,
allowing users to solve TSP instances online.
Definition 8. LKH algorithm [Helsgaun,2009]: LKH is an effective implementation of the LinKernighan heuristic [Lin and Kernighan,1973] for solving the traveling salesman problem. Computational
7

experiments have shown that LKH is highly effective. LKH has produced optimal solutions for all solved
problems they have been able to obtain; including a 85,900-city instance (at the time of writing, the largest
nontrivial instance solved to optimality). Furthermore, the algorithm has improved the best known solutions for a series of large-scale instances with unknown optima, among these a 1,904,711-city instance (called
World TSP).
Both Concorde [Concorde, 2003] and LKH [Helsgaun,2009] solve all 110 TSPLIB instances [Reinelt,1991] to
optimums.

Table 2: 5 Longest Running Time TSPLIB Instances Solved Exactly by LKH [Helsgaun,2009]

Name

#Nodes

Running Time (Seconds)

fl1577
fnl4461
u1817
pcb3038
pla7397

1577
4661
1817
3038
7397

10975
10973
2529
3237
130220

Table 2 shows that LKH results for 5 STSP TSPLIB instances which are top 5 longest running time
instances for LKH solved in 1998 and running times are measured in seconds on a 300 MHz G3 Power
Macintosh.
5. Conclusions and Future Work
In this paper, we provide an algorithm ITGBC in polynomial time with absolute approximation bounded
solutions for TSP. One can see from Table 1 that, the scale (the number of nodes) of TSP is increased as year
increasing; one of reasons for the TSP to become harder is because of the scale becomes larger and larger.
For TSPLIB instances with node number less than 5000, ITGBC based on LKH can solve them to optimality
in less than a few hours or shorter. These mean that ITGBC can provide exact or approximation-bounded
solutions to practical TSPs.
How about other NP problems? Can they also be solved in similar way? According to Karp’s result
[Karp,1972] that if any of NP problems have efficient algorithms, then they all do. Hopefully our proposed
approach can shine light on other NP problems.
Acknowledgments
This research is partially supported by China National Science Foundation (CNSF) with project ID
61672136, 61650110513; and Xi Bu Zhi Guang Project (R51A150Z10). A version of manuscript is posted on
arxiv at https://arxiv.org/abs/1605.06183.
References
References
[1] Clay Mathematics
problems.

Institute,

http://www.claymath.org/millennium-problems/millennium-prize-

[2] Stephen Cook (1971). The Complexity of Theorem Proving Procedures, Proceedings of the third annual
ACM symposium on Theory of computing. pp. 151158, March of 1971.
[3] William Cook, In Pursuit of the Traveling Salesman, Princeton University Press, 2012.

8

[4] Concorde, http://www.math.uwaterloo.ca/tsp/concorde.html
[5] William I. Gasarch, (June 2002). The P=?NP poll
doi:10.1145/1052796.1052804. Retrieved 2008-12-29.

,

SIGACT News 33 (2):

34-47.

[6] William I. Gasarch, The Second P=?NP poll, SIGACT News 74, 2012.
[7] K. Helsgaun,General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming
Computation, 2009,doi: 10.1007/s12532-009-0004-6.
[8] Richard M. Karp (1972), Reducibility Among Combinatorial Problems, In R. E. Miller and J. W.
Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85-103.
[9] S. Lin, B.W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem. Oper.
Res.21, 498-516 (1973).
[10] LKH codes, http://www.akira.ruc.dk/∼keld/research/LKH/, last accessed Jan. 15th of 2015.
[11] Christos H. Papadimitriou, The Euclidean travelling salesman problem is NP-complete, Theoretical
Computer Science, Volume 4, Issue 3, June 1977, Pages 237-244.
[12] Christos H. Papadimitriou and Santosh Vempala, On the approximability of the traveling salesman
problem,Combinatorica 26 (1) (2006) 101-120.
[13] G. Reinelt. TSPLIB, a traveling salesman problem library. ORSA Journal on Computing, 3(4):376-384,
1991.
[14] S. Reiter and D. B. Rice. Discrete optimizing solution procedures for linear and nonlinear integer
programming problems. Management Science, 12(11):829-850, 1966.
[15] David Soler, A transformation for the mixed general routing problem with turn penalties,Journal of the
Operational Research Society 59, 540-547, April 2008.
[16] Wenhong Tian, Chaojie Huang, Xinyang Wang, A Near Optimal Approach for Symmetric Traveling
Salesman Problem in Eclidean Space, To appear in Proceedings of ICORES 2017, Portugal, also available
at arxiv https://arxiv.org/pdf/1502.00447.pdf
[17] Wikipedia, http://en.wikipedia.org/wiki/NP-complete.
[18] http://www.win.tue.nl/∼gwoegi/P-versus-NP.htm
[19] Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, IIT Kanpur, Preprint of August 8,
2002, http://www.cse.iitk.ac.in/news/ primality.html.
[20] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388,
Graduate School of Industrial Administration, CMU, 1976.
[21] Sanjeev Arora, Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other
Geometric Problems. J. ACM 45(5):753-782,1998.

9

