Alex's Notes

❯

❯

NP-hard

Nov 02, 20231 min read

programming

NP-hard

A problem is NP-hard if for all search problems there is a many-one reduction from to . In other terms, is as hard as any search problem.

Graph View

Backlinks

Week 10 - Graph problem complexity
Week 10 - NP overview
Week 12 - Max-SAT approximation algorithm
Week 10 - Feature selection
3-SAT is NP-complete
Clique of a given size problem is NP-complete
Independent set of a given size is NP-complete
Integer linear programming is NP-hard
Knapsack-search is NP-complete
Max clique problem is NP-hard
Max independent set problem is NP-hard
Max-SAT is NP-hard
Minimum vertex cover problem is NP-hard
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