Alex's Notes

❯

❯

NP-Complete

Oct 27, 20231 min read

programming

NP-Complete

A problem is NP-complete if

is NP, and

is NP-hard.

Graph View

Backlinks

Week 10 - Graph problem complexity
Week 10 - NP overview
Week 10 - NP-completeness
Week 12 - Knapsack complexity
Week 13 - Known NP-complete problems
3-SAT is NP-complete
Clique of a given size problem is NP-complete
Independent set of a given size is NP-complete
Knapsack-search is NP-complete
SAT is NP-complete
Subset-sum problem is NP-complete
The k-colourings problem is NP-complete
Vertex cover of a given size is NP-complete
k-SAT is NP-complete for k greater than or equal to 3

Created with Quartz v4.5.1 © 2025

GitHub
Discord Community