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.

- What is the formal definition of Θ(f(n)) without expressing Θ(f(n)) in terms of O(f(n)) or Ω(f(n))?
- Big O notation of string permutation in Python
- Why log(n!) is O(nlog(n)) and not O(log(n!))
- What are the differences between NP, NP-Complete and NP-Hard?
- finding the time complexity of the program
- Why is the knapsack problem pseudo-polynomial?
- How to implement the Sosic and Gu linear algorithm for the n-queens problem
- What is O(log* N)?
- Calculating the Recurrence Relation T(n)=T(n-1)+logn
- Time complexity of a recursive function with three recursive calls
- Divide and Conquer max profit algorithm
- Time complexity versus space complexity in Turing machines
- Time complexity of unshift() vs. push() in Javascript
- Does overwriting an existing array with a new array cost extra time or memory in the context of complexity analysis?
- Find the number of steps a string can be reduced to 0
- How to find the set of binary symbols that can most efficiently compress using Huffman coding?
- For a certain problem if I have a O(f1(m,n)) algorithm and a O(f2(m,n)) algorithm, can I have a O(min(f1(m,n),f2(m,n))) algorithm?
- Do you use Big-O complexity evaluation in the 'real world'?
- Running time complexity of the function
- Find optimal combination of items with 2 values
- Why is array element referencing a constant time operation?
- Specialized SAT solver (?)
- What is the time complexity of java.util.HashMap class' keySet() method?
- Both of the functions' space complexity is O(1) but the one is better than other one?_?
- Can you asymptotically analyze C libraries?
- Complexity analysis of SelectionSort
- What is the fastest algorithm to find an element with highest frequency in an array
- Finding the first n largest elements in an array
- How to calculate tight bounds for asymptotic computational complexity for functions with subroutines?
- Cost of len() function