NP-Hard and NP-Complete Problems
- The class of problems “NP-complete stands for the sub-lass od decision problems in NP that are hardest.
- The class NP-complete is abbreviated as NPC and comes from:
- Non-deterministic polynomial
- Complete-“Solve one, solve them all”
- A decision problem L is said to be NP-Complete if:
- L is in NP that means any given solution to this problem can be verified quickly in polynomial time.
- Every problem is NP reducible to L in polynomial time.
- It means that if a solution to this L can be verified in polynomial time then it can show to be in NP.
- A problem that satisfies the second condition is said to be NP-hard that will examined in recent.
- Informally it is believed that if an NPC problem has a solution in polynomial time then all other NPC problems can be solved in polynomial time.
The list given below is the examples of some well-known problems that are NP-complete when expressed as decision problems.
- Boolean circuit satisfiability problem(C-SAT).
- N-puzzle problem.
- Knapsack problem.
- Hamiltonian path problem.
- Travelling salesman problem.
- Subgraph isomorphism problem.
- Subnet sum problem.
- Clique Decision Problem (CDP).
- Vertex cover problem.
- Graph coloring problem.
- The following techniques can apply to solve NPC problems and they often give rise to substantially faster algorithms:
- Approximation Approach.
- iii. Restriction.
- Parameterization. v. Heuristics.
The class NP-hard written as NPH or NP-H stands for non-deterministic polynomial time hard. The class can define as:
- NPH is a class of problems that are “At least as hard as the hardest problems in NP”
- A problem H is NP-hard if there is an NPC problem L that is polynomial time reducible to H (i.e. L H).
- A problem H said to be NPH if satisfiability reduces to H.
- If an NPC problem L can solve in polynomial time by an oracle machine with an oracle for H.
NP-hard problems are generally of the following types-decisions problems, search problems, or optimization problems.
To prove a problem H is NP-hard, reduce a known NP-hard problem to H.
If an NPH problem can solve in polynomial time, then all NPC problems can also solve in polynomial time. As a result, all NPC problems are NPH, but all NPH problems are not NPC.