NP-Complete and NP-Hard Problems

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:

• Wikipedia
• Paul Dunne’s Annotated List
• A compendium by Viggo Kahn and others (Royal Institue of Technology)
• A graph showing how new problems were discovered to be NP-Hard

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?