## 21 problems of Karp :

- Satisfiability
- Clique
- Set packing
- Vertex cover
- Set covering
- Feedback arc set
- Feedback node set
- Directed hamiltonian circuit
- Undirected hamiltonien circuit

- Clique
- 0-1 integer programming
- 3-SAT

The problems of operational research, and more generally of the decision making, are often Np-complete, that is to say that we do not know any algorithms allowing to find an optimal solution in polynomial time, but we know how to obtain a feasible solution in polynomial time.

## Polynomial complexity

An algorithmhave a polynomial complexity if there exists a polynom 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 have a 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 affect complexity.

## Polynomial reduction

A decision problem P is reduced to a decision problem P’ if there exists a polynomial algorithm R that transforms any input u of P into an input 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.