Problemas industriales y reducción de polinomios 101

I. Reducción y presentación de los 21 problemas de Karp

Satisfacción
- Hacer clic
  - Establecer embalaje
  - Cubierta de vértice
    - Establecer cubierta
    - Conjunto de arco de retroalimentación
    - Conjunto de nodos de comentarios
    - Circuito hamiltoniano dirigido
      - Circuito hamiltoniano no dirigido
Programación de números enteros 0-1
3-SAT
- Número cromático
  - Haga clic en la portada
  - Cobertura exacta
    - Coincidencia 3D
    - Árbol de Steiner
    - Golpeando el set
    - Mochila
      - Secuencia de trabajos
      - Dividir
        Max-corte

Contenido

Reducción de polinomios

Los problemas de la investigación operativa, y más en general de soporte de decisiones suelen ser Np-completos, es decir que no conocemos algoritmos que permitan encontrar una solución óptima en tiempo polinomial, pero sabemos cómo obtener una solución factible en polinomio. tiempo (por reducción polinomial).

Complejidad polinomial

Los problemas son decidibles, es decir, el problema se puede formular de tal manera que la respuesta sea Sí o No. La complejidad de sus problemas se considerará en el peor de los casos.

a algoritmo es de complejidad polinomial si existe un polinomio P tal que el número de instrucciones elementales realizadas durante su ejecución en una instancia de tamaño n es como máximo P(n). Un problema es de complejidad polinomial si existe un algoritmo de complejidad polinomial que lo resuelve. Es importante recalcar que la representación de las estructuras de datos utilizadas no influye en la complejidad.

Reducción de polinomios

Un problema de decisión P se reduce a un problema de decisión P 'si existe un algoritmo polinomial R que transforma cualquier entrada u de P en una entrada u' = R (u) de P 'tal que u∈Sí (P) ⇔ u'∈ Si p ').

Esto sugiere la siguiente implicación: si hay un algoritmo polinomial para P ', también hay uno para P.