¿Qué es la reducción del tiempo polinomial?

La idea es que si

• cualquier instancia de L1 puede transformarse en una instancia de L2
• cualquier instancia de L2 se puede resolver de manera eficiente, utilizando algún truco ingenioso

entonces L1 se puede resolver de manera eficiente utilizando cómo se puede expresar en términos de L2.

Lo que idealmente querría es tomar todas las instancias de algún problema conocido y terriblemente difícil y convertirlo en una representación que permita resolverlo. “SAT

A la inversa, es mucho menos interesante: “L

La forma correcta es reducir la satisfacción de L, y dado que la satisfacción se conoce como NP completo (Cook), concluya que una solución de L también es una solución a todos los problemas de NPC. Es al menos tan difícil como cualquier cosa en NP, es decir, NP-hard. También puede ser más difícil que el NPC, ya que reducirle un NPC solo le da un límite inferior.

Si también demuestras que L está en NP, también has demostrado que no es más difícil que NPC, y entonces también debe ser NPC.

Para comenzar con la reducción del tiempo polinomial, el tiempo requerido para reducir un problema a otro es polinomial.
Ahora tomemos un ejemplo:
Considera que tienes dos problemas: L1, L2

Ahora, cuando digo que L1 es

En términos de programación, se verá así:

  soluciones nulas L2 (L2 l2)
 {
        // resuelve la instancia dada de L2
 }

 PolyReduction L2 (L1 l1)
 {
        // Haz algunas operaciones
        devuelve l1 en forma de L2;
 }

 nula SolvesL1 ()
 {
       L2 l2 = PolyReduction (esto);  // Convierte L1 para que parezca L2
       Resuelve L2 (l2);  // Ahora Resolver L2 significa que resolviste L1
 }

Tiempo requerido para resolver L1:
Primero reducimos L1

Espero que ayude

He estado tratando de entender esta cosa P vs NP por un tiempo, y una de las razones por las que fue difícil entenderlo es obviamente entender la Reducción del tiempo polinomial. quiero decir Lo que básicamente necesitaba, supongo, es ver un ejemplo concreto o algo así como una reducción de tiempo polinómica, tal vez incluso algo de código …

Y eso es exactamente lo que encontré en el curso en línea de Udacity “Introducción a la informática teórica”.

Introducción a la informática teórica

---

Investigué MUCHO sobre la teoría P vs NP durante semanas y el curso en línea es realmente la forma más fácil y divertida que encontré para entender todo. (y muchas otras cosas sobre informática teórica)

En ciencias de la computación, esto es cuando postulas que existe un algoritmo de tiempo polinómico que resuelve algún problema de tiempo no polinómico. Luego puede usar esto para demostrar que varios problemas son de igual o mayor complejidad.

Un ejemplo suelto sería si tuviera un algoritmo X para resolver algún problema y no supiera que es complejo. Entonces podría suponer que tiene un algoritmo Y tiene una solución de tiempo polinomial para el vendedor que viaja. Si puede mostrar que el algoritmo X puede resolverse en tiempo P dado Y. Podría decir que X está en NP en virtud de la reducción del tiempo polinómico.