# Questions from the NP-complete chapter

Posted by Gavin Rens
Announcements Last Post
myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Questions from the NP-complete chapter January 01, 2006 12:12PM IP/Host: ---.absamail.co.za Registered: 13 years ago Posts: 1 Rating: 0
Hello all,

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.

Regards
Gavin Rens
Sorry, only registered users may post in this forum.