Search code examples
complexity-theorypolynomial-mathnp

Authentic List of NP, NP Complete and NP Hard problems

After wading through multiple sources, fol list has been prepared by me. But this seems confusing and overlapping. Pl validate or share a resource with authentic list:-

    NP Problems:
1.  Hamiltonian Path Problem
2.  Subset Sum Problem
3.  Graph Isomorphism Problem
4.  Boolean Satisfiability Problem (SAT)
5.  Vertex Cover Problem
6.  Knapsack Problem
7.  3-SAT Problem
8.  Clique Problem
9.  Traveling Salesman Problem (TSP)
10. Maximum Independent Set Problem

NP-Complete Problems:
1.  Boolean Satisfiability Problem (SAT)
2.  Traveling Salesman Problem (TSP)
3.  Knapsack Problem
4.  Graph Coloring Problem
5.  Hamiltonian Cycle Problem
6.  Subset Sum Problem
7.  3-SAT Problem
8.  Steiner Tree Problem
9.  Bin Packing Problem
10. Vehicle Routing Problem

 NP-Hard Problems:
1.  Halting Problem
2.  Post Correspondence Problem
3.  Knapsack Problem
4.  Graph Coloring Problem
5.  Hamiltonian Cycle Problem
6.  Steiner Tree Problem
7.  Bin Packing Problem
8.  Vertex Cover Problem
9.  Independent Set Problem
10. Partition Problem
Solution

  • By definition, every NP-complete problem is also NP, and NP-hard. And many problems (but not all) in NP are NP-hard. So overlap is not only allowed, but also expected.

    For example, the clique (decision) problem is NP-complete, meaning it is also NP and NP-hard, so it should be in all of your lists.

    However, that doesn't make your list of examples incorrect, unless you claim it to be a complete and exhaustive list of all problems in these categories. This would be impossible because there exists an infinite number of problems so you cannot list them.