El algoritmo de asignación aleatoria puede ser aleatorizado (hecho determinista) usando el método de expectativas condicionales.
Deje que la instancia de 3SAT consista en las cláusulas . Durante el algoritmo asignaremos valores a las variables. La puntuación de una cláusula se define de la siguiente manera:C1, ... ,CmetroC
- Si está satisfecho, entonces su puntaje es 1.C
- Si C no está satisfecho y tiene k literales sin asignar, entonces su puntaje es 1 -2- k .
Inicialmente, el puntaje de cada cláusula es , por lo que el puntaje total es . Ahora asignamos valores a las variables en orden. Supongamos que hemos asignado valores a las variables , y la puntuación total actual es . Sea la puntuación total si asignamos los valores (respectivamente) a . que para cualquier cláusula , y así . En efecto:1 -2- 3= 7 / 8( 7 / 8 ) mX1, ... ,XnorteX1, ... ,Xi - 1S= S(C1) + ⋯ + S(Cmetro)S0 0,S10 , 1XyoS0 0( C) +S1( C) = 2 S( C)CS0 0+S1= 2 S
- Si está satisfecho (solo dado ) o no contiene entonces .CX1, ... ,Xi - 1XyoS0 0( C) +S1( C) = 2 S( C)
- Suponga que contiene literales no asignados, incluido . Entonces , y . Por tanto,
CkXyoS( C) = 1 -2- kS0 0( C) = 1 -2- ( k - 1 )S1( C) = 1
S0 0( C) +S1( C) = [ 1 - 2 ⋅2- k] + 1 = 2 ( 1 -2- k) = 2 S( C) .
- Un argumento similar funciona cuando contiene . CX¯yo
Como , o (posiblemente ambos). Por lo tanto hay una cierta asignación a de tal manera que después de la asignación, la nueva puntuación es de al menos .S0 0+S1= 2 SS0 0≥ SS1≥ SSS
El puntaje inicial es el algoritmo asegura que el puntaje nunca disminuya. Al final, el puntaje de una cláusula es 1 si se cumple y caso contrario. Por lo tanto, la asignación final satisface al menos cláusulas.( 7 / 8 ) mC1 -2- 0= 0( 7 / 8 ) m
Dado que existe un algoritmo determinista, ¿por qué nos interesa el aleatorio? Hay varias razones:
- El algoritmo aleatorio es mucho más simple.
- El algoritmo aleatorio es potencialmente más rápido.
- El algoritmo aleatorizado se puede convertir en uno determinista utilizando el método de expectativas condicionales; Podemos considerarlo como una receta para construir un algoritmo determinista.
En términos más generales, se conjetura que cada algoritmo de polytime aleatorizado para un problema de decisión puede ser aleatorizado (esta es la conjetura ). Los algoritmos aleatorios seguirán siendo interesantes por todas las razones enumeradas anteriormente.P=BPP