gds@oahu.cs.ucla.edu (Greg Skinner) (02/05/90)
Rather than answer the original poster's questions individually, I can think of a couple of good books that he (or anyone) who is interested in the subject of NP-completeness can read that give intuitive, simple explanations of the subject. First, read David Harel's _Algorithmics_. Pay close attention to chapters 7 through 9. In those chapters NP-completeness, decidability, and Turing machines are explained. Once you have finished that book, go on to Michael Garey and David Johnson's _Computers and Intractability_. It's all about NP-completeness. They give explanations of what the theory is, how you prove something NP-complete, related results, and a long list of problems with the complexity class they (probably) fall into. A side note: I am glad someone else besides me finds this subject difficult! I have taken two algorithms classes and two computability classes, and sometimes I still have to scratch my head over a problem. It took the reading of both these books, plus a number of other algorithms books, class notes, and MANY, MANY conversations with various people (Hi gang!) before I had a grasp of the subject. As a former co-worker of mine once said, "NP-completeness is a very subtle subject". --gregbo