NP-complete problems #

List of 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
  • A great survey on the potential of using the physical world to solve NP-complete problems.