Problems under NP-Hard Class
- Traveling Salesman Problem (TSP)
- Subset Sum problem
- Knapsack Problem
- Boolean Satisfiability Problem (SAT)
- Graph Coloring Problem
- Independent Set Problem
- 3-SAT Problem
- Vertex Cover Problem
- Bin Packing Problem
- Hamiltonian Cycle Problem
- Partition Problem
- Knights Tour Problem
- Quadratic Assignment Problem
- Clique Problem
NP-Hard Class
A ‘P‘ problem is said to be NP-Hard when all ‘Q’ belonging in NP can be reduced in polynomial time ( where k is some constant) to ‘P’ assuming a solution for ‘P’ takes 1 unit time.
NP-Hard is a computational complexity theory that acts as a defining property for the class of problems that are “at least as hard as the hardest problems in NP”. P’s solution can be used to solve ‘Q’ in polynomial time. For example, the Subset Sum Problem, and Turing Halting problem is an NP-Hard problem.