英文:
Authentic List of NP, NP Complete and NP Hard problems
问题
以下是翻译好的部分：
NP 问题：
- 哈密顿路径问题
- 子集和问题
- 图同构问题
- 布尔可满足性问题（SAT）
- 顶点覆盖问题
- 背包问题
- 3-SAT 问题
- 团问题
- 旅行商问题（TSP）
- 最大独立集问题
NP-完全问题：
- 布尔可满足性问题（SAT）
- 旅行商问题（TSP）
- 背包问题
- 图着色问题
- 哈密顿回路问题
- 子集和问题
- 3-SAT 问题
- 斯坦纳树问题
- 装箱问题
- 车辆路径问题
NP-困难问题：
- 停机问题
- 后继问题
- 背包问题
- 图着色问题
- 哈密顿回路问题
- 斯坦纳树问题
- 装箱问题
- 顶点覆盖问题
- 独立集问题
- 划分问题
英文:
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
答案1
得分: 1
根据定义，每个NP完全问题也是NP和NP-hard。许多问题（但不是全部）在NP中也是NP-hard。因此，重叠不仅被允许，而且是预期的。
例如，团（决策）问题是NP完全问题，这意味着它也是NP和NP-hard，因此它应该在您的所有列表中。
然而，这并不意味着您的示例列表是不正确的，除非您声称它是这些类别中所有问题的完整和详尽列表。这是不可能的，因为存在无限多的问题，所以您无法列出它们。
英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论