Analysis & Design of Algorithms

Q.8: Explain the relationship between class P, NP, NP-complete and NP hard problem with example of each class.

Answer

Class P  If a problem can be solved by a deterministic Turing machine in polynomial time, the problem belongs to the complexity class P. All problems in this class have a solution whose time requirement is a polynom on the input size n. i.e. f(n) is of form akn k +ak−1n k−1 +...+a2n 2 +a1n+a0 where ak, ..., a0 are contant factors (possibly 0). The order of polynom is the largest exponent k such that ak = 0 (if ak = 0, then the polynom is ak−1n k−1+...+a0 and the order is k − 1, unless ak−1 = 0. If ak−1 = 0, too, then the polynom is ak−2n k−2 + ... + a0 etc.).

 

Class NP contains all computational problems such that the corresponding decision problem can be solved in a polynomial time by a nondeterministic Turing machine.

 

NP-complete problems

NP-complete problems are special problems in class NP. I.e. they are a subset of class NP. An problem p is NP-complete, if

1. p NP (you can solve it in polynomial time by a non-deterministic Turing machine) and

2. All other problems in class NP can be reduced to problem p in polynomial time.

 

NP-hard problems are partly similar but more difficult problems than NP complete problems. They don’t themselves belong to class NP (or if they do, nobody has invented it, yet), but all problems in class NP can be reduced to them. Very often, the NP-hard problems really require exponential time or even worse.

Notice that NP-complete problems are a subset of NP-hard problems, and that’s why NP-complete problems are sometimes called NP-hard. It can also happen that some problem which is nowadays known to be only NP-hard, will be proved to be NP-complete in the future – it is enough that somebody just invents a nondeterministic Turing machine, which solves the problem in polynomial time.

 

:


notes For Error Please Whatsapp @9300930012