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
  • 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
Alternar contenido
Alternar contenido

Reducción de polinomios

Los problemas de la investigación operativa, y más generalmente deayuda con la decisión son a menudo Np-completos, es decir, no conocemos ningún algoritmo que permita encontrar una solución óptima en tiempo polinomial, pero sabemos cómo obtener una solución factible en tiempo polinomial (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. los complejidad de sus problemas serán considerados 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 ').

reducción de polinomios 21 problemas de karp

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

Compartir, repartir