🚀 go-pugleaf

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