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