- Satisfiability
- Click
- Set packing
- Vertex cover
- Set covering
- Feedback arc set
- Feedback node set
- Directed hamiltonian circuit
- Undirected Hamiltonian circuit

- Click
- 0-1 interger programming
- 3-SAT
- Chromatic number
- Click cover
- Exact cover
- 3D Matching
- Steiner tree
- Hitting set
- Knapsack
- Job sequencing
- Partition
- Max-cut

- Chromatic number

Contents

Toggle## Polynomial reduction

The problems of operations research, and more generally of decision support are often Np-complete, that is to say that we do not know algorithms allowing to find an optimal solution in polynomial time, but we know how to obtain a feasible solution in polynomial time (by polynomial reduction).

## Polynomial complexity

a algorithm is of polynomial complexity if there exists a polynomial P such that the number of elementary instructions carried out during its execution on an instance of size n is at most P(n). A problem is of polynomial complexity if there is an algorithm of polynomial complexity solving it. It is important to emphasize that the representation of the data structures used does not influence the complexity.

## Polynomial reduction

A decision problem P reduces to a decision problem P' if there exists a polynomial algorithm R which transforms any entry u of P into an entry u'=R(u) of P' such that u∈Yes(P) ⇔ u'∈Yes(P').

This suggests the following implication: if there is a polynomial algorithm for P', then there is also one for P.