4 ms·

Ask HN: an intro to P=NP

2 points by ErrantX 17y ago

Im one of these annoying people that likes to absorb information by reading it (I find it is more sticky that way). So, yes, the P=NP problem. It's always piqued my interest but a lot of the online material is a bit too mathematical for me to handle without some serious revision :) for stuff like this I also prefer book form. But recently I got much more to grips with the idea and it's the kind of thing I'd love to consider properly in idle moments :) Can anyone recommend a really good book on the problem (I'm struggling to find any good recommendations). Something that isn't too math's heavy (or at least reminds you of the basics as necessary) that can walk you through the problem and set out some (non-too-mathematical) examples. Preferably something a bit light-hearted :)

michael_dorfman 17y ago
"The New Turing Omnibus" has a chapter on P=NP, and is a "light hearted, not too maths-heavy" introduction to about 50 other basic problems in CS.
- ErrantX 17y ago
  thanks - exactly what I was after :D
RiderOfGiraffes 17y ago
> recently I got much more to grips with the idea ... Something that isn't too math's heavy ... You're asking for contradictory advice. If you're starting to get to grips with the idea then you want something that goes beyond the basic concepts. OTOH, you're asking not to get into the math. Tricky. Let's start here. Do you know the difference between an instance and a problem? Do you know what it means for a problem to be in P? In NP? Do you know the difference between NP and NPC? Do you know a proof that a problem - any problem - is in NPC? Do you know how you would go about that?
- ErrantX 17y ago
  well ok perhaps I phrased it badly: I have a bit-part overview but now I would like to read about the "problem" in full with not too much maths. As far as I have seen you dont need an awful lot of maths to describe the problem As to the latter set of questions: the answer to most is "vaguely" :) hence needing the reading material :)
  - RiderOfGiraffes 17y ago
    There's quite a good "layman's" explanation of the problem, including some of its history, in Keith Devlin's book "The Millennium Problems." The problem description starts on page 112. In that book he also refers to the official Clay Mathematics Institute (CMI) book that gives a summary, and then the problem in detail. He also references a short film that gives a similar outline summary. The film can apparently be found at http://www.claymath.org http://www.claymath.org I'm sure there are dozens of descriptions of the "Does P=NP?" question on the 'net. Which ones have you read? What was unsatisfactory about them? Name three, tell me what you didn't like, and I'll try to find another for you, or write one myself. Note: I'm not an expert, but if my knowledge is different from yours, perhaps I can help. I have proved directly that graph 3-vertex coloring is in NPC. An outline of the proof is actually here on HN if you'd care to go find it. You still haven't answered my original questions, though.

2 points by ErrantX 17y ago

michael_dorfman 17y ago

"The New Turing Omnibus" has a chapter on P=NP, and is a "light hearted, not too maths-heavy" introduction to about 50 other basic problems in CS.

ErrantX 17y ago
thanks - exactly what I was after :D

RiderOfGiraffes 17y ago

> recently I got much more to grips with the idea ... Something that isn't too math's heavy ... You're asking for contradictory advice. If you're starting to get to grips with the idea then you want something that goes beyond the basic concepts. OTOH, you're asking not to get into the math. Tricky. Let's start here. Do you know the difference between an instance and a problem? Do you know what it means for a problem to be in P? In NP? Do you know the difference between NP and NPC? Do you know a proof that a problem - any problem - is in NPC? Do you know how you would go about that?

ErrantX 17y ago
well ok perhaps I phrased it badly: I have a bit-part overview but now I would like to read about the "problem" in full with not too much maths. As far as I have seen you dont need an awful lot of maths to describe the problem As to the latter set of questions: the answer to most is "vaguely" :) hence needing the reading material :)
- RiderOfGiraffes 17y ago
  There's quite a good "layman's" explanation of the problem, including some of its history, in Keith Devlin's book "The Millennium Problems." The problem description starts on page 112. In that book he also refers to the official Clay Mathematics Institute (CMI) book that gives a summary, and then the problem in detail. He also references a short film that gives a similar outline summary. The film can apparently be found at http://www.claymath.org http://www.claymath.org I'm sure there are dozens of descriptions of the "Does P=NP?" question on the 'net. Which ones have you read? What was unsatisfactory about them? Name three, tell me what you didn't like, and I'll try to find another for you, or write one myself. Note: I'm not an expert, but if my knowledge is different from yours, perhaps I can help. I have proved directly that graph 3-vertex coloring is in NPC. An outline of the proof is actually here on HN if you'd care to go find it. You still haven't answered my original questions, though.