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


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

  • 3
    $\begingroup$ 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). $\endgroup$
    – D.W.
    Jan 18 at 5:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – An5Drama
    Jan 18 at 6:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.