And why solve one of them can solve all,how does it be proved
In: Mathematics
>why NP-complete problem can’t be find optimal solution
It’s not that it cannot be found. But that finding it as far as we know *scales exponentially* This means that the time it takes to solve the problem depends on a number that grows very fast with the size of the problem. It quickly reaches ridiculous values like age of the Universe and we can’t really optimize it with better computers.
To give you the sense of how does the exponential scale grow. Assume, that you can solve the Traveling Salesman Problem for 3 cities in a milisecond. For 10 cities you would need a second. For 35 cities — a year. For 45 cities — a million years.
However we still didn’t *prove* that a better algorithm cannot be found.
>And why solve one of them can solve all
One of the NP-complete problems is the so-called satisfiability problem. The problem is: given some sentence like “a and b or c or (d and e)” etc. find values for all the variables (true or false) that would make the whole expression true. The thing is — we can turn any NP-complete problem into a satisfiability problem. So if we can solve this problem in an efficient way, we will also be able to solve others (this is an intuitive explanation, the formal proof has more CS nuance).
Latest Answers