This course is giving sleepless night:

And I would like to meet with some people in Cape Town to discuss the course,as a study group or something.

We can arrange to meet somewhere ,Southern Surburb(Mowbray side) or Bellvile side.

Or we can form a study group over a charting room like skype(did you know that is possible?this can also include people who are even out of Cape Town,....)

If there is anyone out there needing this kind of help.

Please lets talk,

I really need to discuss my understanding with other people,

maybe I am getting it wrong...or right....?

Thanks

]]>

1. Please confirm my definition of the class NP: "Let Sn be all possible proposed solutions of size n to a problem instance P. If: <<< For each n (ie, for each set of Sn), if there is at least one solution, call it Sc, that is a correct solution, there exists a (deterministic) algorithm A that can verify Sc as correct in polynomial-time >>> then P is in the class NP. When a proposed solution Sx is not correct, Sx need not be verified as incorrect, or can be verified as incorrect in superpolynomial (or polynomial) time. That is, incorrect proposed solutions are not a concern for the classification of problems as NP.

2. Is it so that the value of the class NP is that many 'important', 'naturally occurring' problems can be classified as members of NP (and not always as members of P), which is a convenient way of classifying the complexity of problems that are not (yet) conveniently classified in some other way? And a further value of NP is that it leads to the classification of (some) problems as NP-complete that cannot (as yet) be classified as being in P, are particularly difficult and probably harder than problems in P?

3. One need not know what a specific correct solution to a decision problem is to be able to say whether the problem is in NP. (?)

4. The last line on page 581 (3rd ed.) states that SSC(n) >= n/4 for n >= 4. Please explain how the authors came to this conclusion. (I came to the conclusion that SSC(n) = n/2 for all n: In the worst case (ie, Gk as input), "SC needs a new color for each pair ai and bi" and there are n = k pairs, and opt(SC) = 2.) The explanation will also help clarify for me the use of "worst-case ratios" for algorithms.

]]>