Industrial problems and polynomial reduction

  • Satisfiability
    • Click
      • Set packing
      • Vertex cover
        • Set covering
        • Feedback arc set
        • Feedback node set
        • Directed hamiltonian circuit
  • 0-1 interger programming
  • 3-SAT
    • Chromatic number
      • Click cover
      • Exact cover
        • 3D Matching
        • Steiner tree
        • Hitting set
        • Knapsack
          • Job sequencing
          • Partition
            • Max-cut
Toggle Content

Polynomial reduction

The problems of operational research, and more generally ofhelp with the decision are often Np-complete, that is to say that we do not know any algorithms making it possible 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

Problems are decidable, that is, the problem can be formulated in such a way that the answer is yes or no. The complexity of his problems will be considered in the worst case.

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 input u of P into an input u' = R (u) of P 'such that u∈Yes (P) ⇔ u'∈Yes (P ').

polynomial reduction 21 karp problems

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

To share