2 ms·
> 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
by 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 agowell 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 agoThere'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.