The infamous traveling salesman problem is an NP problem without being a P problem - yet. The problem involves finding the shortest route between some finite number of cities. Furthermore the problem is also proven to be NP complete – which means that all NP problems can be reduced to the traveling salesman problem in polynomial time.
All NP-hard problems are called that not because we know that they cannot be solved in polynomial time, but because we have no proof that they can be. It is completely possible that extremely hard problems (meaning that there algorithmic solutions either do not exist or take too long) are actually really easy ones. We just haven’t found the right method to go about solving them.
The prime factorization problem is considered to be an NP-hard one too. If I give you a number and ask you to provide me with its prime factors, it would and should take you more time than it takes me to verify whether the factorization you provided is correct, and that all the factors are in fact prime (the primality test can be done in polynomial time). This fact is the basis for some widely used encryption methods – methods that keep your money etc safe during transactions etc on the internet.
Now one of the biggest problems in CS and Math involves trying to prove or disprove that P=NP. If P=NP then it can, and must in the optimal solution, take just as long to come up with a solution to those problems the answer of which can be verified in polynomial time as it does to verify them. In other words, everything we thought was hard wasn’t really hard; we were just being stupid.
Obviously, that makes mathematicians, cryptologists, and computer scientists deeply uncomfortable:
“If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...”
— Scott Aaronson
So, because we don’t want to be called stupid more than anything else, the conjecture out there is that P is not equal to NP. Creativity is still awesome. Humanity, and not computers, wins.
Last month, a man called Vinay Deolalikar claimed to have proved that P is not equal to NP. He had a 102 page proof and it made us all very excited. Then someone pointed out “fatal flaws” in his proof. He hasn’t retracted his paper yet, but it seems like he will have to.
Which brings me to my point, finally. Would you rather work ten, twenty years on a really hard problem and not have anything substantial to show for it at the end, or would you rather work ten, twenty years on a really hard problem, come up with a solution, feel on top of the world, and then be told that you are absolutely wrong?
Maheen