# How can the approximation algorithm of one NP-complete problem be used to prove "the class P would be the same as the class NP"?

Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I had some questions about some statements in it.

Fur- thermore, if a polynomial worst-case time complexity algorithm were discovered for the traveling salesperson problem, many other difficult problems would also be solvable using polynomial worst-case time complexity algorithms (such as determining whether a proposition in n vari- ables is a tautology, discussed in Chapter 1). This follows from the theory of NP-completeness.

A practical approach to the traveling salesperson problem when there are many vertices to visit is to use an approximation algorithm. ... That is, they may produce a Hamilton circuit with total weight W′ such that $$W \le W′ \le cW$$, where W is the total length of an exact solution and c is a constant ... If such an algorithm existed, this would show that the class P would be the same as the class NP, perhaps the most famous open question about the complexity of algorithms

I knew that NP can only be "verifiable in polynomial time by a deterministic Turing machine" while P can be solved in polynomial time by a deterministic Turing machine.

Then if we find one approximation algorithm for NP-complete which adds the NP-hard property for NP, then it only approximates instead of solving the problem. If it can solve, then based on NP-complete, all NP problems can be solved.

I also referred to one QA answer which states:

Proving an upper bound on the possible approximation is akin to P=NP

But the answer seems to not answer the reasons behind the relation between the approximation algorithm and $$P=NP$$. This is weaker than the above finding both the lower bound $$W$$ and the upper bound $$cW$$.

Q:

How does the approximation algorithm for one NP-complete problem show that "we can show the existence of an algorithm that solves any given instance of problem in NP in polynomial time", i.e. $$P=NP$$?

• I suggest you search out lecture notes on approximation algorithms and hardness of approximation, which should cover this topic. See also the first paragraph of en.wikipedia.org/wiki/Clique_problem#Hardness_of_approximation and P-Complete Approximation Problems (Sahni & Gonzalez, JACM v23n3 1976).
– D.W.
Jan 18 at 5:51
• Thanks. The 2nd link solves with this problem although it is a bit beyond my ability currently. I will read it more detailedly when I learned targetedly about the complexity theory. Jan 18 at 6:00