Problemas industriales y reducción de polinomios

  • 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

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.

Un 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 sea como máximo P (n). Un problema es de complejidad polinomial si existe un algoritmo de complejidad polinomial que lo resuelva. Es importante enfatizar 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 ').

réduction polynomiale 21 problèmes de karp

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

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: