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 Institute of Technology)
• A graph showing how new problems were discovered to be NP-Hard

Yet Another List

Here are some NP-Hard problems. Many are given in their optimization form, rather than their decision problem form.

SAT

Does a given boolean formula, in CNF, have a satisfying assignment?

3SAT

Does a given boolean formula, in CNF with exactly three literals per clause, have a satisfying assignment?

CIRCUIT SAT

Does a given arbitrary boolean circuit have a satisfying assignment?

MINIMUM VERTEX COVER

In a given undirected graph, what is the (size of the) smallest subset of the vertices covering all of the edges?

MAXIMUM INDEPENDENT SET

In a given undirected graph, what is the (size of the) largest subset of the vertices having no edges in common?

MAXIMUM CLIQUE

What is the (size of the) largest complete subgraph of a given undirected graph?

HAMILTON PATH

Does a given graph have a Hamilton Path?

HAMILTON CYCLE

Does a given graph have a Hamilton Cycle?

GRAPH COLORING

Can the vertices of a given graph be colored with $k$ colors such that no two adjacent vertices share the same color?

3COLORING

Can the vertices of a given graph be colored with 3 colors such that no two adjacent vertices share the same color?

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 integers be partitioned into two subsets each with the same sum?

3PARTITION

Can a given set of $3n$ integers be partitioned into $n$ 3-element subsets each with the same sum?

MINIMUM SET COVER

Given a set $S$ and a collection of subsets of $S$, what is smallest set of these subsets whose union is $S$?

THREE-DIMENSIONAL MATCHING

Given three disjoint sets $X$, $Y$, and $Z$ and a set of triples $T \subseteq X \times Y \times Z$, is there a subset of $T$ of size $n$ such that every element of $X \cup Y \cup Z$ appears in exactly one triple?

MINIMUM 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?

MINESWEEPER

In a given Minesweeper configuration, is it safe to click on a particular square?

SUDOKU

Does a given Sudoku puzzle have a solution?