Supongamos que tomamos una porción de 20 índices del medio, lo que llamamos la “porción de trabajo”.
En el lado izquierdo (con variables con índices más pequeños que el fragmento de trabajo), tenemos algunas cláusulas. Estas cláusulas solo usan variables con índices más pequeños que el fragmento de trabajo y variables en el fragmento de trabajo.
En el lado derecho (con variables con índices más grandes que el fragmento de trabajo), tenemos algunas cláusulas. Estas cláusulas solo usan variables con índices mayores que el fragmento de trabajo y variables en el fragmento de trabajo.
- ¿Se requiere un buen conocimiento de la estructura de datos y algoritmos para saltar a la codificación competitiva?
- ¿Cuál es la conclusión del algoritmo de Dijkstra?
- ¿Es difícil seguir 100 días de algoritmos?
- ¿Hay alguna diferencia entre los algoritmos estocásticos y los probabilísticos?
- ¿Cuál es el papel de la memoria de montón?
Ahora, adivinamos el pedazo de trabajo. Hay como máximo 1048576 formas aquí. Para cada suposición, resolvemos 3-SAT en cada lado de forma independiente. Digamos que se necesita como máximo C (n / 2) tiempo para resolver cada lado.
El tiempo total para resolver el medio es 1048576 * Cn. Ups Tenemos un problema. ¿Qué hicimos mal?
¿Calculamos repetidamente algo?
Para empezar, este problema genera muchos subproblemas similares. Por ejemplo, considere la siguiente división de variables:
A1 W1 A2 W2 A3 W3 A4
Dividimos el problema en el fragmento de trabajo W2. Anotamos las variables fijas de W2 como W2 *.
Ahora necesitamos resolver 3-SAT en las instancias A1 W1 A2 W2 * y W2 * A3 W3 A4.
No hay subproblemas todavía. Dividamos las instancias A1 W1 A2 W2 * en W1.
Tenemos los subproblemas: A1 W1 *, W1 * A2 W2 *
Independientemente de lo que asignemos W2, el subproblema de A1W1 solo depende de W1. Por lo tanto, tendremos subproblemas repetidos cuando separemos el problema. Podemos memorizar las soluciones a estos subproblemas.
¿Cuánto tiempo lleva ahora?
Consideremos la división del problema. El caso base de la división es un fragmento que se parece a W1 A W2, donde W1 y W2 son fragmentos de trabajo (lo que significa que son fijos), y A es un fragmento de variables que son variables cortas (<30). Como esta instancia del problema está limitada, tomaría como máximo una cantidad de tiempo constante para probar todas las entradas, multiplicado por el número de cláusulas en el caso base.
Supongamos que dividimos el problema en casos base B. Cada uno de estos casos tendrá conjuntos de cláusulas disjuntas para tener en cuenta. Calcularíamos 2 ^ 20 * 2 ^ 20 resultados, lo que llevaría una cantidad de tiempo constante por n, n es el número de cláusulas.
¿Cómo combinamos los subproblemas?
Continuamos mostrando que la combinación de casos base toma como máximo un tiempo constante n cantidad de tiempo en total. Claramente, B = O (n), ya que hay como máximo 3n variables, y B está limitado por el número de variables.
Para combinar los dos primeros casos base, probamos todas las entradas posibles para el fragmento de trabajo que los separa. Necesitamos probar 2 ^ 20 valores para el fragmento de trabajo (en este caso, W1).
A1 W1 * A2 W2
Además, necesitamos resolver el problema para todos los casos de W2. Esto toma como máximo 2 ^ 20 * 2 ^ 20 operaciones para decidir todos los valores 2 ^ 20 de W2, y 2 ^ 20 decisiones para que W1 combine el subproblema para cada W2.
Por lo tanto, generamos 2 ^ 20 valores, que recordaríamos.
Entonces, combinar dos subproblemas requiere como máximo un número constante de operaciones. Hay O (n) subproblemas para combinar, por lo que necesitamos combinar O (n) veces, por lo tanto, necesitamos como máximo operaciones O (n) para combinar todos los subproblemas.
Cuando terminamos de combinar los subproblemas, resolvemos la instancia original.
Por lo tanto, tenemos una solución para este tipo de problema en tiempo lineal (por supuesto, con un factor constante grande debido al número 20).
