In: Computer Science
What is NP? What is P? What is NP-complete? What is NP- hard? Give brief definitions. Give an example of an NP- complete problem. Is P equal to NP?
SOLUTION-(4):-
P : P belongs to the set of all decision problems which we can solved in polynomial time by a deterministic Turing machine. Because, it can be solved in polynomial time, it can also be verified in polynomial time. Therefore P is a subset of NP.
NP : NP belongs to the set of all decision problems where instances of the problem for which the answer is yes have proofs that can be verified in polynomial time. That means that if someone gives us an instance of the problem and a certificate (sometimes called a evidence) to the answer being yes, we can examine that it is correct in polynomial time. NP denotes to the Non-deterministic Polynomial time.
NP-Complete : An NP problem A for which it is possible to reduce any other NP problem B to A in polynomial time. Instinctively that means that we can solve B quickly if we know how to solve A quickly. Precisely, B is reducible to A if there is a polynomial time algorithm z to transform instances b of B to instances a = z(b) of A in polynomial time with the property that the answer to b is yes iff the answer to z(b) is yes.
NP-Hard : Instinctively these are the problems that are even harder than the NP-complete problems. NP-hard problems do not require to be in NP (they do not require to be decision problems). The precise definition here is that a problem A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. But because any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then if there exist is a solution for one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.
The 3SAT problem is an example of NP-Complete problem : It denotes to solving the satisfiability problem for an expression in 3CNF form.
Is P equal to NP : Every decision problem that we can solve by a deterministic polynomial time algorithm is also solvable by a polynomial time non-deterministic algorithm. We can solve all problems in P with polynomial time algorithms, whereas all problems in NP - P are intractable. It is not known whether P = NP. Although, many problems are known in NP with the characteristic that if they belongs to P, then it can be proved that P = NP. If P ≠ NP, there exists some problems in NP that are neither in P nor in NP-Complete. The problem belongs to class P if it is easy to search a solution for the problem. The problem belongs to NP, if it is easy to examine a solution that might have been very exhausting to search.