## NP-complete problems #

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