NP, P, NP-complete and NP-Hard problems?

306 views

posted Nov 30, 2013

+1 vote

P problems are questions that have a yes/no answer and can be easily solved by a computer. For example, determining whether a number is prime is a relatively easy problem to solve.

NP problems are questions that have yes/no answers that are easy to verify, but are hard to solve. And by hard, I mean it would take years, decades or centuries for your computer to come up with an answer.
For example, the travelling salesman problem is trying to figure out the shortest trip through a bunch of cities, visiting each city only once.
Let's say you ask me the question, can I visit these 500 cities in my state and spend less than 3000 miles on the road? If I magically show you an itinerary that takes you to all those 500 cities, you can easily verify whether that itinerary is less than 3000 miles. BUT, trying to come up with that itinerary in the first place is really hard for computers.

NP-complete problems are special kinds of NP problems. You can take any kind of NP problem and twist and contort it until it looks like an NP-complete problem.
For example, the knapsack problem is NP. It can ask what's the best way to stuff a knapsack if you had lots of different sized pieces of different precious metals lying on the ground , and that you can't carry all of them in the bag.
Surprisingly, there are some tricks you can do to convert this problem into a travelling salesman problem. In fact, any NP problem can be made into a travelling salesman problem, which makes travelling salesman NP-complete.

NP-Hard problems are worst than NP problems. Even if someone suggested you a solution to a NP-Hard problem, it'd still take forever to verify if they were right.
For example, in travelling salesman, trying to figure out the absolute shortest path through 500 cities in your state would take forever to solve. Even if someone walked up to you and gave you an itinerary and claimed it was the absolute shortest path, it'd still take you forever to figure out whether he was a liar or not.