Registered: 13 years ago
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.