# NP-complete problems

1. The clique problem
2. The vertex-cover problem
3. The hamiltonian-cycle problem
4. The traveling-salesperson problem
5. The subset-sum problem
6. Reduction strategies

- wiki
1. Boolean satisfiability problem (SAT)
1. Knapsack problem
1. Hamiltonian path problem
1. Travelling salesman problem (decision version)
1. Subgraph isomorphism problem
1. Subset sum problem
1. Clique problem
1. Vertex cover problem
1. Independent set problem
1. Dominating set problem
1. Graph coloring problem

## 0. 本周提到的 NP-complete 問題有那些
1. 0/1 Knapsack problem
2. traveling salesperson problem
3. partition problem
4. art gallery problem

## 1. The clique problem