NP-Complete and NP-Hard Problems
There are so many.
Review the Definitions
P is the set of all decision problems solvable in polynomial-time.
NP is the set of all decision problems whose YES answer is checkable in polynomial-time.
co-NP is the set of all decision problems whose NO answer is checkable in polynomial-time.
A problem is NP-Hard iff a polynomial-time solution for it would
imply a polynomial-time solution for every problem in NP.
A problem is NP-Complete iff it is NP-Hard and it is in NP itself.
Lists
Lots of folks have made lists of NP-Complete and NP-Hard Problems. Here are a few:
Yet Another List
Here are some of my favorite NP-Hard problems:
- SAT
- Does a given boolean forumla, in CNF, have a satisfying assignment?
- 3-SAT
- Does a given boolean forumla, in CNF with exactly three literals per clause, have a satisfying assignment?
- Min Vertex Cover
- In a given undirected graph, what is the (size of the) smallest subset of the vertices covering all of the edges?
- Max Independent Set
- In a given undirected graph, what is the (size of the) larges subset of the vertices having no edges in common?
- Max Clique
- What is the (size of the) largest complete subgraph of a given undirected graph?
- Min Set Cover
- Given a set $S$ and a collection of subsets of $S$, what is smallest set of these subsets whose union is $S$?
- Min Hitting Set
- Given a set $S$ and a collection of subsets of $S$, what is smallest subset of $S$ containing at least one element from every subset?
- Hamilton Path
- Does a given graph have a Hamilton Path?
- Hamilton Cycle
- Does a given graph have a Hamilton Cycle?
- Traveling Salesperson
- What is the minimum cost Hamilton Cycle in a weighted, complete, graph?
- Longest Path
- What is the longest path between two given nodes in a weighted, undirected, graph?
- Subset Sum
- Does a given set of positive integers have a subset with sum $k$?
- Partition
- Can a given set of positive integers be partitioned into two subsets each with the same sum?
- 3-Partition
- Can a given set of $3n$ positive integers be partitioned into $n$ 3-element subsets each with the same sum?
- Minesweeper
- In a given Minesweeper configuration, is it safe to click on a particular square?
- Sodoku
- Does a given Sodoku puzzle have a solution?