Hi mom! Okay, this is it! First, sit down, take a deep breath. Have some tea. This is gonna hit you hard. Okay, here goes.
People have found out that some problems are much easier to solve with a computer than others. They have given names to groups of problems depending on how hard or easy they are. Makes sense? Okay.
The first group of problems is called P. Problems in P can be solved by a computer in a reasonable amount of time. Example: sorting a list of names is not so much work for a computer. You can remember it like this: "Easy PEE-sy!" right?
Not much to say about those. They're the boring run of the mill problems. We are going to look at the interesting stuff.
The next group, called NP, contains problems for which a computer can quicklycheck a proposed solution. So all P problems are also NP problems: if you can solve it, you can check it, but not necessarily the other way around. So you can remember NP like this: "NOPE! Not so easy!" An example of an NP problem is: "Given this city map, is there a route of length X that visits all these addresses"? Given such a route, it's easy to check, but it's not easy to find one.
Okay mom, this was sort of reasonable, right? But now it gets a little weird. Because as it turns out, there are some problems that we don't know how to solve efficiently, but if we could, then we could use the solution to immediately solve all other problems in NP. This holy grail of computing is called the group of NP-hard problems. Finding a route of length X via a set of addresses is an example of an NP-hard problem: it would be extremely cool if someone were able to figure out how to do it efficiently (but don't hold your breath). If you figure out how to solve an NP-hard problem efficiently you will be a millionaire. Everyone will want to touch you. For real!
Some NP-hard problems are so hard, their solutions cannot even be checkedefficiently; so confusingly these problems are not always in NP themselves. To rule those bad boys out, people call the group of NP-hard problems that are still easy to verify "NP-complete" problems.
Okay mom. Now I know you really want to run away and do something real. But you can't yet, because I still have to tell you about the biggest mystery in computer science, which is this: no-one knows if the picture I have just drawn for you is correct: no-one knows if there are NP-complete problems that are not also in P! Everyone is completely and utterly convinced that these exist, but no one has been able to prove it. Chew on that!
--
Steven de Rooij
https://www.quora.com/What-is-an-explanation-of-P-versus-NP-problems-and-other-related-terms-in-laymans-terms
People have found out that some problems are much easier to solve with a computer than others. They have given names to groups of problems depending on how hard or easy they are. Makes sense? Okay.
The first group of problems is called P. Problems in P can be solved by a computer in a reasonable amount of time. Example: sorting a list of names is not so much work for a computer. You can remember it like this: "Easy PEE-sy!" right?
Not much to say about those. They're the boring run of the mill problems. We are going to look at the interesting stuff.
The next group, called NP, contains problems for which a computer can quicklycheck a proposed solution. So all P problems are also NP problems: if you can solve it, you can check it, but not necessarily the other way around. So you can remember NP like this: "NOPE! Not so easy!" An example of an NP problem is: "Given this city map, is there a route of length X that visits all these addresses"? Given such a route, it's easy to check, but it's not easy to find one.
Okay mom, this was sort of reasonable, right? But now it gets a little weird. Because as it turns out, there are some problems that we don't know how to solve efficiently, but if we could, then we could use the solution to immediately solve all other problems in NP. This holy grail of computing is called the group of NP-hard problems. Finding a route of length X via a set of addresses is an example of an NP-hard problem: it would be extremely cool if someone were able to figure out how to do it efficiently (but don't hold your breath). If you figure out how to solve an NP-hard problem efficiently you will be a millionaire. Everyone will want to touch you. For real!
Some NP-hard problems are so hard, their solutions cannot even be checkedefficiently; so confusingly these problems are not always in NP themselves. To rule those bad boys out, people call the group of NP-hard problems that are still easy to verify "NP-complete" problems.
Okay mom. Now I know you really want to run away and do something real. But you can't yet, because I still have to tell you about the biggest mystery in computer science, which is this: no-one knows if the picture I have just drawn for you is correct: no-one knows if there are NP-complete problems that are not also in P! Everyone is completely and utterly convinced that these exist, but no one has been able to prove it. Chew on that!
--
Steven de Rooij
https://www.quora.com/What-is-an-explanation-of-P-versus-NP-problems-and-other-related-terms-in-laymans-terms
Thanks Sajjad. It was very interesting and communicative text.
ReplyDeleteI think we need these sort of tutorials to transfer the core idea of complex concepts to the people who are not from the same discipline. This way, they can understand what is going on in the field, then if it attracts them, they can go deeper. At least it can help them to figure out how they could think about other problems in a very easy intuitive way.
ReplyDelete