Propósito de la aleatorización/desaleatorización en el algoritmo aleatorio básico para MAX SAT

Question

En las Secciones 5.1 de El diseño de algoritmos de aproximación. por Williamson y Shmoys, describen un algoritmo aleatorio básico para MAX SAT y cómo desaleatorizarlo.El algoritmo consiste simplemente en asignar a cada variable 1 (verdadero) con probabilidad 1/2 y 0 (falso) con probabilidad 1/2.En otras palabras, tome muestras aleatorias y uniformes del espacio de todas las soluciones.Muestran que esto es una aproximación 1/2.

Luego, en la Sección 5.2, describen cómo desaleatorizarlo utilizando el método de expectativas condicionales.(No describiré el proceso aquí porque supongo que no es muy complejo y ampliamente conocido).

Mi pregunta es, ¿por qué molestarse en desaleatorizar de esta manera?O incluso, ¿por qué molestarse en hacer que el algoritmo sea aleatorio en primer lugar?

Me parece que un algoritmo igualmente bueno sería el de una sola línea que establece de manera determinista todas las variables en 1.Dada alguna instancia de MAX SAT como entrada, me parece que también se esperaría que esto (es decir, "se espera que") satisfaga la mitad de las cláusulas.Para mí, el análisis del algoritmo aleatorio realmente parece decir que cualquier conjetura fija es "buena". (En lugar de mostrar que nuestro algoritmo aleatorio es inherentemente bueno). Entonces, ¿por qué pasar por el proceso de aleatorización y desaleatorización en primer lugar?

¡Gracias de antemano!

Answer 1

La diferencia es que el algoritmo aleatorio garantiza una aproximación 1/2 esperada. en cualquier entrada.Por el contrario, es fácil para un adversario construir una entrada (es decir,una instancia de MAX-SAT) para el cual el algoritmo determinista "establecer todas las variables en verdadero" satisface cero cláusulas.

Recuerde que el espacio muestral de un algoritmo aleatorio está formado por un conjunto de bits aleatorios auxiliares.No se asume ninguna distribución de probabilidad sobre el entradas.El objetivo típico del diseño de algoritmos aleatorios es que cada entrada se maneje bien según las expectativas.(El análisis del comportamiento del algoritmo sobre una distribución de entrada supuesta se llama análisis de caso promedio en cambio.)

¿Qué son los bits aleatorios auxiliares?

Supongamos que tenemos una máquina de Turing aleatoria $M_1$ que se ejecuta en instancias de longitud $n$ por no más de $T(n)$ tiempo, durante el cual no produce más de $R(n)\le T(n)$ decisiones aleatorias.Podemos convertir esta máquina en una determinista máquina de Turing $M_2$ que tiene dos cintas de entrada:la cinta habitual que contiene la cadena de entrada $x$ de longitud $n$, y una cinta que contiene una cadena $r$ de longitud $R(n)$.La cuerda $r$ es nuestra cadena de bits aleatorios auxiliares;determina qué decisiones "aleatorias" debe tomar la máquina de Turing.Cuando decimos que la máquina de Turing aleatoria funciona $M_1(x)$ acepta con probabilidad $p$, esto equivale a decir que el conjunto$$A(x) = \left\{r\ |\ r \in \{0, 1\}^{R(|x|)}, M_2(x, r) ext{ acepta} ight\} $$de $r$ cuerdas que hacen $M_2(x,r)$ aceptar constituye una fracción $p = |A(x)| / 2^{|x|} $ del conjunto de todos $r$ instrumentos de cuerda.

Es posible que reconozca lo que está sucediendo aquí si ha visto la construcción análoga de las máquinas de Turing no deterministas.Podemos pensar en una máquina NP como una máquina no determinista que se bifurca en un número exponencial de copias de sí misma.Pero también podemos considerarlo como una cuestión determinista. verificador máquina que requiere tanto una entrada como una cadena de "prueba", con el criterio de aceptación de que una cadena de entrada esté en el idioma si cualquier La cadena de prueba hace que la máquina acepte.

A menudo es más fácil pensar en este concepto realista de máquinas verificadoras deterministas y qué subconjunto de cadenas de prueba hace que la máquina acepte una entrada determinada, en lugar de pensar en ideas muy abstractas como máquinas con ramificaciones exponenciales y mundos posibles.Y facilita la definición de clases de complejidad como co-NP, PP, BPP, ⊕P, etc., todas las cuales son esencialmente "NP con una regla de aceptación diferente". Por ejemplo:

• NP es el conjunto de lenguajes $l$ para lo cual existe una máquina verificadora de tiempo polinomial $M_2$ tal que $x \en L$ si y sólo si existe una $r$ cuerda tal que $M_2(x,r)$ acepta (donde la longitud del $r$ la cadena está limitada por un polinomio $R(|x|)$).
• BPP es el conjunto de lenguajes $l$ para lo cual existe una máquina verificadora de tiempo polinomial $M_2(x,r)$ tal que $x \en L$ implica que $M_2(x,r)$ acepta al menos ⅔ de $r$ cuerdas y $x ota L$ implica que $M_2(x,r)$ acepta como máximo ⅓ de $r$ cuerdas (donde la longitud de la $r$ cuerdas está limitada por un polinomio $R(|x|)$).

Nota:En general, no importa si necesitamos el $r$ cuerdas para tener longitud exactamente $R(n)$ o a lo sumo $R(n)$, ya que permitir cadenas más cortas solo aumenta el número de cadenas posibles en un factor constante.