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.)
I’ve been trying to understand this myself, but I think there’s a lot of nuance in mathematics that, as a programmer, I don’t understand. This is my best guess at it though:
If you have a question and a list of possible answers, you need to look through some or all of the answers to see which (if any) is correct…
If you can look at one of the answers and know, just by looking at it alone, that it’s the correct answer to the question, it’s “P” complexity. Basically a for-loop over the answers.
If, for each answer you look at, you need to look at all other answers and compare them to know whether the answer you’re looking at is correct, it’s in “NP” complexity. This is called NP because, as I understand it, in mathematics “non-deterministic” seems to mean, branch a new machine to solve each answer in parallel, and though you don’t know ahead of time which machine will return the answer (non-deterministic) you’ll get the answer back from one of them in “P” time. But without infinite machines to branch in programming, this is basically a nested for-loop looping all the the answers again, for each answer.
If, for each answer you look at, you need to look at all other answers, and for each one of those, need to look at all other answers repeatedly, never knowing if you’ll come to a solution, it’s “NP hard”. Basically an infinite loop to a regular computer.
If, for each answer you look at, you need to look at all other answers, and for each one of those, need to look at all other answers repeatedly, but you do know it will eventually come to a solution, it’s “NP complete”. Looks like an infinite loop to a regular computer, but actually, the answer will fall out some time this side of infinity.
But again, not a mathematician.
Latest Answers