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).
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.
I’m not sure what the question in your title means, but I’ll answer the second one.
So, we’re looking at two categories of problems – P and NP. Without getting into much details, P problems are problems that can be solved quickly (i.e. you can write a relatively efficient computer program that finds a solution). NP problems are problems that, given a proposed solution, we can check quickly whether this solution is correct.
Now, lets say we have two problems, lets call them A and B. If we can write an efficient program that will translate an input to problem A to an input to problem B and then translate the solution of problem B to a solution of problem A, we say that problem A can be *reduced* to problem B. This basically means that if we found a solution to B, it also serves as a solution to A.
A problem is called “NP-complete” if every problem in NP can be reduced to it. Suppose we have some problem in NP-Complete (let’s call it L). If we want to solve some other problem in NP, we can just reduce the problem to L and then solve L. If we manage to find an L that can be solved easily, then it means that we can easily solve any problem in NP. If L happens to be in P, then it means that every problem in NP is also in P, which means P=NP.
Have to share one of my favorite videos on YouTube which helped me understand P=NP https://youtu.be/YX40hbAHx3s?si=-WgOGTjGc5u-bsHh
Some problems can be *solved* quickly. “What is 114889 times 288689?”, for example.
Some problems can be *checked* quickly. “Is 33167190521 the result of multiplying the two prime numbers 114889 and 288689?”, for example.
Some problems which can be *checked* quickly, cannot be *solved* quickly. “Which two prime numbers did I multiply together to get 33167190521?”, for example.
There are some types of problems which are fundamentally very complex, and (as far as we know) there may well not be a simple solution at all. Even if there IS an efficient solution, it is clear at this point that it requires some profound breakthroughs in mathematics. We don’t just need to improve our computations, we need new approaches to these problems fullstop.
For a long time it was hoped that someone would crack P vs NP, and discover the P=NP, but that never happened. It was hoped that perhaps quantum computers might help somehow, but that never happened.
Really this is rubbing up on the boundaries of what mathematics can answer – Why are some problems hard? A question which I am unqualified to answer.
[removed]
Latest Answers