# Polynomial reduction

## 21 problems of Karp :

• Satisfiability
• Clique
• Set packing
• Vertex cover
• Set covering
• Feedback arc set
• Feedback node set
• Directed hamiltonian circuit
• Undirected hamiltonien circuit
• 0-1 integer programming
• 3-SAT
• Chromatic number
• Clique cover
• Exact cover
• Matching 3D
• Steiner tree
• Hitting set
• Knapsack or in PDF
• Job sequencing
• Partition
• Max-cut

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

The problems are decidable, the problem can be formulated in such a way that the answer is Yes or No. The complexity of its problems will be considered in the worst case.

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.

Publicités