There are two group in which problem can be classified. The first group consist of the problem that can be solved in polynomial time. The second group consist of problem that can be solved in non deterministic polynomial time.
Definition of P :-
Problem that can be solved in polynomial time. ( ' P ' stands for polynomial).
Example is searching of key elements ,sorting of elements.
Definition of NP :-
Problem that can be solved in non deterministic polynomial time . ( ' NP ' stands for non polynomial). Example is travelling salesperson , graph coloring problem ,knapsack problem , Hamiltonian circuit problem.
The NP class problem can be further categorized into Np complete and NP hard problems.
NP complete problem :-
- A problem D is NP complete if -
- It belongs to class NP.
- Every problem in NP can also be solved in polynomial time.
- All NP complete problem are Np hard but all NP hard problem cannot be NP complete.
- If an NP hard problems can be solved in polynomial time then all Np complete problem can also be solved in polynomial time.
- The NP class problems are the decision problems that can be solved by non deterministic polynomial algorithms.
NP hard problem :-
NP hard problem are difficult to solve in deterministic polynomial time . However , we call still solve such hard problem by relaxing the restriction on them . Such NP hard problem are called simplified hard problems. Following are few such problems.
- Determining whether a planar graph is three colorable is NP hard .
- Generating optimal code for given expression is NP hard.
- CNF (conjuctive normal form) satisfiability problem with three literals is NP hard.
