All of the answers provided online explain it in terms of other weird terms from discrete math I don’t understand. I’m writing an essay on solutions for the traveling salesman problem for my school, but I’m still just getting started with Discrete Math. While doing my research, I found that the traveling salesman problem belongs to the NP-complexity, but I have no idea what that means.
In: Mathematics
Different algorithms may solve a problem with different efficiency. When sorting a list of numbers for example, the bubblesort algorithm has time-complexity of O(n^(2)). This means that when the list with n elements, the algorithm takes at roughly n^2 time to complete. The mergesort algorithm on the other hand has time-complexity of O(n*log(n)), so it sorts a list with n elements in roughly n*log(n) time. This statement is generally less exact when n is small and becomes more exact as n gets bigger. As n^2 will always eventually surpass n*log(n), this makes mergesort have lower time-complexity as bubblesort.
This works for any kind of complexity, so you might look at how much memory is used, which would be space-complexity instead of time-complexity, or you might look at something different altogether. The common category for these is complexity.
P complexity refers to algorithms that solve a problem in polynomial time. As n^2 is a polynomial, this makes bubblesort with O(n^(2)) have a time-complexity in P. Now, n*log(n) certainly isn’t a polynomial. However, because there exists a polynomial that always eventually surpasses n*log(n) (n^2 is such a polynomial, as explained above), n*log(n) is still regarded to be in P (for polynomial).
Let’s talk about problems instead of algorithms for a moment. When a problem has an algorithm that solves the problem in polynomial complexity, i.e. that the problem can be solved in polynomial complexity, then that problem is in P. Slower algorithms don’t matter, because you can always make an algorithm slower.
When trying to solve the traveling salesman problem (TSP), you will find that no algorithm will ever solve it in polynomial time. That is to say, every algorithm that solves TSP has non-polynomial complexity, it’s complexity will always eventually surpass any polynomial you might compare it to. Thus, TSP is considered to have NP (for non-polynomial) complexity.
In short, problems that are in NP are much less efficient to solve than problems in P. TSP being in NP means that no “efficient” solution for it exists. (Not though that while a solution in P might be regarded as efficient in this context, it might not necessarily be everyday-efficient or practicably usable efficient.)
Latest Answers