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 a_{k}n
^{k} +a_{k−1}n ^{k−1 }+...+a_{2}n
^{2} +a_{1}n+a_{0} where ak, ..., a_{0}
are contant factors (possibly 0). The order of polynom is the
largest exponent k such that a_{k} = 0 (if a_{k} =
0, then the polynom is a_{k−1}n ^{k−1}+...+a_{0}
and the order is k − 1, unless ak−1 = 0. If a_{k−1 }= 0,
too, then the polynom is a_{k−2}n ^{k−2} + ... + a_{0}
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