I dislike the common implication that NP complete means "the stupidest brute force thing is the best way we know how to solve the problem." For example, meet in the middle will turn subset sum from 2^n to 2^(n/2).
P vs NP on simple english wikipedia - feedback, please
41–50 of 66 posts
Re: P vs NP on simple english wikipedia - feedback, please
#42Rating 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 pr…
I would agree that the math required is not 'complicated' from the point of view of anyone with basic understanding of discrete logic, but it's certainly too complicated to express in simple english terms that are understandable at the level i was shooting for.
if you want to do the proof that all problems in P are also in NP, you have to explain the notion of a decision problem and show that any np-complete numerical optimization problem can be converted to a decision problem without increasing its computational complexity by more than a function bounded by a polynomial.
someone named 'balabiot' changed the article by adding an incorrect 'proof' that P is a subset of NP, at the same time you made this post. the incorrect proof reads:
All P problems are NP problems: if a problem is easy to
solve, to check an answer you just solve it and check that
the results match.
note that simply solving the problem (because it is in p) is NOT the same thing as verifying a solution correct.
Re: P vs NP on simple english wikipedia - feedback, please
#43I 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…
Thanks Mark,
Good work Indeed.
Can you please explain why you think P=NP. I am deeply interested in knowing about them.
Re: P vs NP on simple english wikipedia - feedback, please
#44I dislike the common implication that NP complete means "the stupidest brute force thing is the best way we know how to solve the problem." For example, meet in the middle will turn subset sum from 2^n to 2^(n/2).
i agree that there are a lot of problems, but the goal of this article was to make the topic as simple as possible. any simplification of a complex, mathematical construct will invariably result in hand-waving and undefined terms; i tried my best to keep those to a minimum. i plan to expand the article in the future, to clarify some mathematical details. thanks for the feedback, though.
Re: P vs NP on simple english wikipedia - feedback, please
#45Earlier quoted context omitted.
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 a…
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 instincts are often wrong, and the story of science will probably never be finished.
Re: P vs NP on simple english wikipedia - feedback, please
#46My 2c: Don't write "Problems in P", write "P Problems". Also you definition of "why its interesting" conflicts with the other Wikipedia page which says: The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.
i'm not sure i see the conflict... care to elaborate?
Re: P vs NP on simple english wikipedia - feedback, please
#47Earlier quoted context omitted.
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 a…
N^(1,000!!!!) is P but you need a rediculusly large number before 2^(N) is worse (N >= 2). Generally N^5 is about as far as you want before you can do anything with 3 digit numbers.
Re: P vs NP on simple english wikipedia - feedback, please
#48i 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 the ability to pose the question:
> Many people want to know if there are any NP problems that are not P Problems
Re: P vs NP on simple english wikipedia - feedback, please
#49Earlier quoted context omitted.
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 a…
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 atoms in the universe does contain a practical infinity.