3 ms·
i guess the article is currently being edited, but at the moment it isn't so clear what is common and what different between the two groups. i think it would b
by andrewcooke 15y ago
i guess the article is currently being edited, but at the moment it isn't so clear what is common and what different between the two groups. i think it would be better if the motivation came earlier:
solving a problem is sometimes harder than checking you have the right answer.
for example, it is easy to check that you have the secret key to a code. you
can decode a message and see the original text. but it is hard to find the key
if you do not know it.
so the problem of finding the key to a code is much harder than checking whether a
key is correct. other problems can be easy to solve and to check. for example,
adding 2 and 2 is both easy to solve and to check.
this difference can be used to divide problems into two groups. these groups are
called P and NP. it is easy to check the answers for problems in both groups,
but only problems in group P are easy to solve.
the problem of adding two numbers is in P, because it is easy to solve and to
check. the problem finding a secret key to a code is in NP because is is easy to
check but hard to solve.
i know my writing isn't simple enough here, but an approach like the above makes it easier to understand the relationship between them. in particular, the commonality between the two groups is emphasised.
- Wilduck 15y agoI had a similar response to the article, but I can see at least one reason why this explanation doesn't fit. Despite any inclinations we may have P vs. NP is still unsolved. So, claiming that a problem is in NP is "easy to check but hard to solve" is not necessarily true (if P == NP, it is both easy to check and to solve). The original article does a good job of not making this assumption, and because of this gains the ability to pose the question: > Many people want to know if there are any NP problems that are not P Problems
- andrewcooke 15y agohmmm. it's true that my text is wrong in that way, but couldn't you fix it with a "maybe" or "appear" and then explain the open question afterwards? or maybe the conditional nature of the text then becomes too complex?