Week 13 - NP-complete problems
The following problems are known to be NP-complete:
- Lectures
- SAT problem - SAT is NP-complete
- k-SAT - k-SAT is NP-complete for k greater than or equal to 3
- Independent set of a given size - Independent set of a given size is NP-complete
- Clique of a given size problem - Clique of a given size problem is NP-complete
- Vertex cover of a given size - Vertex cover of a given size is NP-complete
- k-colourings problem (graphs) - The k-colourings problem is NP-complete
- Knapsack-search - Knapsack-search is NP-complete
- Subset-sum problem - Subset-sum problem is NP-complete
- Book
- Traveling salesman problem (search) - ???
- Rudrata cycle problem - ???
- Balanced cut problem - ???