Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

P vs NP on simple english wikipedia - feedback, please

simple.wikipedia.org

Post reply on HN
Print view View original

31–40 of 66 posts

Re: P vs NP on simple english wikipedia - feedback, please

#31

Post by andrewcooke »

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.

Re: P vs NP on simple english wikipedia - feedback, please

#32

Post by generelativity »

peteretep wrote: post #6

Your example at the end - you should go in to less detail about the number of combinations, and more in to how it's easy for a computer to check the right answer has been reached.

This. It's a really great example, but you never make the full connection by explaining that it's easy to check that 2 towers have the same mass.

Re: P vs NP on simple english wikipedia - feedback, please

#33

Post by kamaal »

I came from an electronics background when I first started reading algorithms my head was spinning. And I am sure a lot of other novices/laymen from the same problem.

The reason I have seen over the years is simple. Expressing the problems in terms of mathematical equations. Mathematical equations some how denote a way of modifying elements through equations. They tend to build on existing established principles of maths. There fore in order to understand what the other person is saying a person must get into a high learning curve.

When I first read about P Vs NP problem, I really wasn't able to co relate it to anything in the real world. Later on as I read more on puzzles like The Bin packing problem, or the traveling salesman problems. Things began to make sense.

The way to explain people about such things is to give them problems defined in simple English. And then allow them to build their own way of representing objects and elements, and the way they choose to modify them. Like this article does, However while explaining to people start from very small input sizes. Help them work out outputs for large input sizes.

Given the problem at hand, explain them why such large computation time doesn't make sense in the physical world.

Representing the problem in pure math will never help the guy next to your home. Giving him a day to day use case, will force him to think.

So here we go, what all common every day use cases fit into the P Vs NP problem? If we can create such a list, a lot more laymen can think and build on those problems easily!

Is there such a list lurking somewhere?

Re: P vs NP on simple english wikipedia - feedback, please

#34

Post by kamaal »

MarkPNeyer wrote: post #30
mseebach wrote: post #28

I wonder if there is a good way to explain that the nature of these problems is to find any and all exact solutions to the puzzle and that the 95% solution which is vastly easier and entirely sufficient for any practical application (in terms of the given examples) is NOT interesting. E.g.: Travelling sales-person: In terms of P/NP, she doesn't care if she can as much as if there is any possible route she might take…

your claim that a 95% solution is entirely sufficient only applies to numerical optimization problems. every numerical optimization problem has a corresponding decision problem, and an algorithm that could solve these decision problems would be tremendously useful. think about circuit satisfiablility; if you're building an airplane, you want to know if the circuits for the airplane could ever cause the engines to shu…

Although I understand what your are trying to say here.

But the problems you tend to describe never exist in the real world either. What I mean to say is, you can never be Boolean sure about anything in the real world as you can never control all the parameters yourself.

Which in case you are always going to measure things in percentages like x% safer or y% safer.

I guess that's what the parent poster tends to imply.

Re: P vs NP on simple english wikipedia - feedback, please

#36

Post by MarkPNeyer »

kamaal wrote: post #33

I came from an electronics background when I first started reading algorithms my head was spinning. And I am sure a lot of other novices/laymen from the same problem. The reason I have seen over the years is simple. Expressing the problems in terms of mathematical equations. Mathematical equations some how denote a way of modifying elements through equations. They tend to build on existing established principles of m…

doubtful. a programmer could spend an entire career in industry and never run into an np complete problem he needed to solve.

i added more examples to the article, and made them as simple and practical sounding as possible, but to be honest my primary interest in the problem is mostly from a theoretical perspective. to me, the idea that P != NP implies a host of bizarre conclusions that seem incredibly unlikely to me. i am so convinced of this that i had it emblazoned my license plate:

http://www.markpneyer.com/wp/about-me/

Re: P vs NP on simple english wikipedia - feedback, please

#37

Post by nsimplex »

You might want to mention P VS NP is similar to the following scenario: people feel they can identify a piece of art (say a painting) as being of merit very quickly just by seeing it; but won't be able to come up with any piece of equal merit even if they had all the time in the world.

Re: P vs NP on simple english wikipedia - feedback, please

#38

Post by prtk »

Rating 3/10. I don't think this article is written by someone who knows the topic well.

e.g. you don't too complicated math as claimed in this line:

>> It is known that all P problems are NP problems; the proof requires math which is too complicated for this article but may be explained in the future.

For P problems can be solved easily and then the solution can be easily verified. This means all P problems are NP problems too.

Good news!! Better Article Exists. Read: http://cstheory.stackexchange.com/questions/5188/explain-p-n...

Re: P vs NP on simple english wikipedia - feedback, please

#40

Post by Udo »

MarkPNeyer wrote: post #27
Udo wrote: post #24

Many people want to know if there are any NP problems that are not P Problems. That means they would like to know if there are any problems where the answer is hard to find, but if someone says he has the answer, it is easy to check if that answer is correct. This is probably the core of the article, but I find it misleading. The truth is that we need to either prove that the answer to a certain problem will always b…

the lack of a known polynomial time algorithm could be interpreted as evidence that P =/= NP, but it could just as easily be interpreted as evidence of our primitive state of knowledge with regard to algorithms. Suppose that P = NP, but the minimum complexity of any NP-Complete problem is O(n^(# of atoms in the universe)); we might never discover such a complicated algorithm, but that in no way implies it doesn't exi…

I like mine better ;-)

Your idea about the the primitive state of our algorithm knowledge is interesting. This has nothing to do with the article, but I do believe there are deep philosophical implications here. If we knew (and could make use of the fact) that everything is P, it would fundamentally shift our relationship with reality. I would go so far as to say that P =/= NP is an instinctive model we have formed about the universe as it presents itself today. If this were to change, it would affect pretty much everything we're doing - I can't even begin to imagine what would happen on the day abstract problem solving becomes a P algorithm...

Post reply on HN