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

51–60 of 66 posts

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

#51

Post by andrewcooke »

Wilduck wrote: post #48
andrewcooke wrote: post #31

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 t…

I 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 t…

hmmm. 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?

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

#52

Post by orenmazor »

I see posting this here as a mistake. You should post it somewhere where people dont know anything about it. Posting it here will result in us adding more and more detail, possibly making it more complicated.

I used to use my grandmother as a subject for testing out paper abstracts/intros for this reason. She could barely figure out scrolling.

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

#53

Post by corin_ »

bnegreve wrote: post #29
Singletoned wrote: post #16

Earlier quoted context omitted.

In what way is the word 'size' wrong?

I guess that Lamby means that one should not use "weight" instead of "mass", the two being two very different concepts.

They're very different concepts, but for the sake of the example it doesn't matter which you are measuring, you could equally be measuring the number of atoms in each one if you happen to know it.

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

#54

Post by prof_hobart »

As someone who has an interest in this kind of thing, but very little in the way of formal education on it (my last formal maths education was my 'A' levels around 25 years ago), I'm possibly the exact target audience for this article.

Given that, I thought it was very helpful. I've read a whole host of attempts to explain it before, and they rapidly descend into 1000 other mathematical concepts that I don't fully understand and end up reading about instead of the actual P v NP issue.

The one bit that I think is missing is a better explanation of what's meant by "easy" in this context. Clearly a problem that takes more than the life of the universe to solve is likely to classify as hard. But what about if it was solvable in a year, or a minute, or a second? My vague understanding is that there's not really a "less than 5 seconds to solve"-type cutoff, and that it's actually to do with "nondeterministic polynomial time". But at that point I disappear into one of the mathematical things that I don't really grasp.

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

#55

Post by MarkPNeyer »

kamaal wrote: post #43
MarkPNeyer wrote: post #36

Earlier quoted context omitted.

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…

Thanks Mark, Good work Indeed. Can you please explain why you think P=NP. I am deeply interested in knowing about them.

to be honest, mostly it's because i enjoy disagreeing with people who are convinced of things they don't have a full understanding of. if you are decently educated, you realize how much there is we don't know, and approach every unsolved puzzle with a combination of curiosity, confidence and humility. philosophy aside, here's my thinking:

LONG VERSION: Suppose P is an NP complete decision problem; for each instance, the answer is either 'yes' or 'no'. Let P have verifying function V. Let the language L be the set of all binary strings s that represent instances of P for which V(s) = 1, i.e. the set of all strings s that represent instances of P for which the answer is 'yes'. If L (the set of all instances of P for which the answer is 'yes') is finite, then you can easily answer all instances of the problem P in constant time by using a lookup table that stores all members of L (i.e. all finite languages are regular.)

So, consider the case when L is infinite. We know that V must be expressible in terms of a finite sequence of symbols. Suppose we have manged to express V using a total of C bits. The entropy of all C-bit binary sequences is bounded by a function of C alone; i.e. it is independent of the specific content of V, all that matters is how many bits are in some (it doesn't matter which) implementation of V. My primitive understanding of information theory tells me that if V has a finite amount of information, and L is uniquely determined by V, then L cannot possibly have MORE information than V; if you have V and enough time, you can compute all of L. This limits the possibilities of L, and suggest to me that there must be a way to find a (possibly complex and incomprehensible algorithm) for solving all instances of P, by 'compressing' L in just the right way. I admit that this is very hand-wavey; i just don't know enough information theory to pin everything down.

SHORT VERSION: if you can verify all solutions to a problem using a function expressible using a finite sequence of symbols, then the total information content of a sequence representing all solutions to the problem can't exceed the information content of the verifying algorithm.

if P != NP, this (to me) implies that a list of answers to a problem somehow has more information than an algorithm that can be used to generate that list of all answers. it seems to me that the algorithm could easily contain more information than the list, but not the other way around.

to put it another way, if you see a verifying function as a compression algorithm on the list of all solutions (because they contain the same amount of information), then P != NP implies that some infinite sequences (which represent np complete problems) are simultaneously so redundant that they can be compressed to a finite length, but at the same time are so complicated that you can't figure out an arbitrary element without doing a massive amount of computation. as i see it, some patterns can appear random unless you look at them from just the right perspective, and then the pattern emerges. because np-complete problems can be expressed with a finite amount of information, there has to be a pattern that we're not seeing yet.

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

#56

Post by MarkPNeyer »

Udo wrote: post #49
MarkPNeyer wrote: post #45

Earlier quoted context omitted.

what happens in the example i gave above? if the minimum complexity of solving any np-complete problem is O(n^2e80) then we'd need such massively parallel computing that you'd have to turn pretty much every atom in the universe into a computing device. i agree that p != np is the instinctive model most theoreticians have about the universe, but if science has taught us anything in the last 100 years, it's that our in…

Absolutely, but I'd say that the idea of brute-forcing the entire universe - while theoretically and mathematically sound - goes against the spirit of what we're trying to express with Big O. Solutions like these work in a theoretical universe with infinite matter and possibly over infinite time, but if the world is indeed finite (which it may very well be) any Big O expression containing the sum of all states of all…

i'm not sure what you mean by the 'spirit' of Big-O; i find the question fascinating because it is relatively easy to understand the concepts involved, yet it's been 40+ years since we understood enough to be able to ask the question, and we still don't know the answer. when you couple that with the fact that the prevailing wisdom that our inability to find an algorithm implies that it can't exist, the contrarian in me goes nuts: the academic attitude is always "we're so smart, if we can't find it, it must not exist," and i get a kick out of arguing for more humility on their part.

even though a polynomial-time algorithm with a massive polynomial would still be computationally intractable, even a proof that such an algorithm exists, but is too complicated to express using all the atoms in the universe as bits would probably open the doors to all kinds of proofs and techniques we cant' even imagine.

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

#57

Post by MarkPNeyer »

prof_hobart wrote: post #54

As someone who has an interest in this kind of thing, but very little in the way of formal education on it (my last formal maths education was my 'A' levels around 25 years ago), I'm possibly the exact target audience for this article. Given that, I thought it was very helpful. I've read a whole host of attempts to explain it before, and they rapidly descend into 1000 other mathematical concepts that I don't fully un…

i agree, it could use more math. i plan to add that in; my concern is that i don't want to scare people away.

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

#58

Post by MarkPNeyer »

kamaal wrote: post #34
MarkPNeyer wrote: post #30

Earlier quoted context omitted.

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.

you can never control all of the parameters yourself, true, but think of it this way:

the cockpit of an airplane has hundreds of switches and nobs. suppose we want to ask the question "is there some way the pilot could toggle switches or flip knobs that would open the doors in flight?" you're never going to be able to guarantee that the doors won't open, but you can guarantee that the circuit alone won't cause them to open.

or, consider that many games are np-complete. if you are playing such a game against another player, whoever gets the better solution will win.

in addition, the original author's claim that the 95% solution is "vastly easier and entirely sufficient" _may_be true for the numerical optimization problems given in the example, but there are most certainly np-complete problems which cannot be approximated to any degree of accuracy.

for example: given a graph, the max-clique problem asks 'what is the largest fully-connected subgraph?' this problem arises very naturally in social networks; it's equivalent to asking 'what is the largest group of people who are all friends with each other?' This problem cannot be approximated within ANY bound of the optimal solution unless P = NP. The same problem arises in computational biology and chemistry as well.

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

#60

Post by mseebach »

MarkPNeyer wrote: post #58
kamaal wrote: post #34

Earlier quoted context omitted.

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.

you can never control all of the parameters yourself, true, but think of it this way: the cockpit of an airplane has hundreds of switches and nobs. suppose we want to ask the question "is there some way the pilot could toggle switches or flip knobs that would open the doors in flight?" you're never going to be able to guarantee that the doors won't open, but you can guarantee that the circuit alone won't cause them t…

That's a very good point, but my concern is that the provided examples dumb down issues to a level where this is not easily understood. I mean, who gets closer to grasping this nuance bu supposing a woman building towers of rocks on the beach?

Actually, I think the cockpit-switches-example would be a valuable example.

Post reply on HN