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

21–30 of 66 posts

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

#21

Post by rnadna »

Many people find it difficult to see which of two large numbers is greater, unless they are reading on paper and take up a pencil and count the groups of three. This issue must come up a lot in simple-English. The solution is to introduce scientific notation, and to have a link to that. (As has been pointed out, mass is a tricky word, being used here.) Perhaps another method would be to invent something quirky, saying perhaps "4+(20 digits)" or something.

In this particular case, there is another solution: do not quote the individual numbers, but only their ratio. Anyone can tell that "1000" is big and "1/1000" is small, because all that's needed is to see if there are more than two or so digits.

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

#22

Post by mitko »

ilcavero wrote: post #17
hypersoar wrote: post #15

I suggest emphasizing that problems that can be solved easily can be checked easily. It's a simple idea, but it wouldn't necessarily occur to the casual reader and is quite important.

agreed that the example is not the best, a better example would be a picture puzzle that can be verified in just a glance but to build it you need to test all pieces against each other to see if they match.

Picture puzzle is in P because you can build the puzzle incrementally in quadratic time

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

#24

Post by Udo » 

  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 be hard to find (hence proving that P =/= NP) or we need to prove that all NP problems have in theory a P algorithm (P = NP). We currently have many NP (="easily" verifiable) problems that have no known solving algorithm in polynomial time. The evidence would so far suggest that P =/= NP, but this is empirical not mathematical. It's possible that all those non-P problems have some way to resolve them in P, but it doesn't look like it right now.

I would thus rephrase the core explanation as something like this:

"For problems where the correct answer can be checked easily, there are two possibilities: If (P = NP) is correct, that means there is always an easy way to come up with a solution no matter how complicated the problem is. If the opposite is correct (P =/= NP), there are some problems where the answer will always be difficult to find no matter how clever the solution is. We don't know yet which one of these possibilities is true."

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

#25

Post by tspiteri »

DanWaterworth wrote: post #4

I think you might be missing the point of the simple English wikipedia. It's the vocabulary that you use that is simple, not the way in which you express the concepts.

The Simple English Wikipedia is also for people with different needs. Readers may be students, children, and adults who may find it hard to learn, and people who are trying to learn English. Other people use the Simple English Wikipedia because the simple language helps them understand difficult ideas or topics they do not know about.

From: http://simple.wikipedia.org/wiki/Simple_English_Wikipedia

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

#26

Post by Triumvark » 

  P problems are considered 'easy' for computers to solve. NP problems are considered easy for computers to check the answers to them.
To improve clarity:

1. Avoid putting pronouns far from the main noun.

2. Use simple sentences. Reduce the number of verbs and prepositional phrases per sentence.

3. Avoid scare quotes. If you need to qualify a term, do so explicitly.

Consider, for the above:

NP problems have answers which can be easily checked. P problems can be easily solved.

(Maybe precede or follow with a quick definition of what you mean by 'easy.' But I'm not sure it's necessary here.)

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

#27

Post by MarkPNeyer »

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 exist.

still, i see your point, but i think your phrasing is too complicated; i've changed it to this:

  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. 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 cannot easily be found by a computer, but
  if someone says he has the answer, it is easy to use
  a computer to check if that answer is correct.

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

#28

Post by mseebach »

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 that is even an inch shorter than the one she can fairly trivially plan out.

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

#30

Post by MarkPNeyer »

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 shut off mid-flight. the concept of an approximation algorithm is meaningless here; either you know the answer, or you don't.
Post reply on HN