And why solve one of them can solve all,how does it be proved
In: Mathematics
They _can_ be solved optimally, but only in Polinomial time if you already know the answer(afawk). That means, the amount of steps you need to look for the solution is n to the power of something (n being the number of input values to the problem, eg points to visit in the traveling salesman), but you’d need to test all steps simultaneously. This cannot be done by our currently existing computers, which need to do one step after the other – which means the actual time needed to find the solution increases super fast with each added input value.
The “solve one solve all” thing is done by showing that a given problem can be solved this way (it’s then called “NP hard”) and that there is a simple way to transform it into another problem of which we know it’s NP complete. Simple here means “fast enough to not matter compared to solving the problem” – ie you can transform the new problem into an existing one, solve that, transform it back, and you get the solution with the transformation taking little enough time to not matter overall.
Latest Answers