¿Por qué la aleatoriedad tiene un efecto más fuerte en las reducciones que en los algoritmos?

Se conjetura que la aleatoriedad no extiende el poder de los algoritmos de tiempo polinomiales, es decir, se conjetura que ${\bf P}={\bf BPP}$ se mantiene. Por otro lado, la aleatoriedad parece tener un efecto bastante diferente en las reducciones de tiempo polinomiales . Por el conocido resultado de Valiant y Vazirani, $SAT$ reduce a $USAT$ través de la reducción aleatoria del tiempo polinómico. No es probable que la reducción pueda ser aleatorizada, ya que produciría ${\bf NP}={\bf UP}$ , lo que se considera poco probable.

Me pregunto, ¿cuál podría ser la razón de esta situación asimétrica: la desrandomización parece bastante posible en algoritmos de tiempo polinomiales probabilísticos, pero no en reducciones de tiempo polinomiales probabilísticos?

Primero, déjenme comentar sobre el caso específico de la reducción Valiant-Vazirani; espero que esto ayude a aclarar la situación general.

La reducción Valiant-Vazirani se puede ver / definir de varias maneras. Esta reducción está "intentando" asignar una fórmula booleana satisfactoria a una F ′ satisfactoriamente única , y una F insatisfactoria a una F ′ insatisfactoria . Todas las fórmulas de salida siempre se obtienen restringiendo aún más F , por lo que la insatisfacción siempre se conserva. La reducción se puede definir o bien como la salida de un único F ' , o como salida una lista de F ' 1 , ... , F ' t . En el último caso, "éxito" en el caso F $F$$F'$$F$$F'$$F$$F'$$F'_1, \ldots, F'_t$ se define como tener$F \in SAT$ al menos un exclusivamente satisfactoria en la lista. Llame a estas dos variantes "reducción de singleton" y "reducción de lista" respectivamente (esto no es terminología estándar).$F'_i$

El primer punto que es importante tener en cuenta es que la probabilidad de éxito en la reducción de singleton es bastante pequeña, es decir, donde n es el número de variables. Las dificultades para mejorar esta probabilidad de éxito se exploran en el documento.$\Theta(1/n)$$n$

"¿La probabilidad de aislamiento de Valiant-Vazirani es mejorable?" por Dell et al.

http://eccc.hpi-web.de/report/2011/151/#revision1

En la lista de reducción, la probabilidad de éxito puede hacerse grande, digamos, con un poli ( $1 - 2^{-n}$lista de tamaño ) . (Uno puede simplemente repetir la reducción de singleton muchas veces, por ejemplo).$(n)$

Ahora, no es del todo evidente o intuitivo que podamos ser capaces de desrandomizar directamente una reducción que solo tiene probabilidad de éxito . De hecho, ninguno de los resultados de dureza versus aleatoriedad da hipótesis bajo las cuales podemos hacerlo en este caso. Es mucho más plausible que la reducción de la lista pueda ser aleatorizada (con una lista algo mayor). Sin embargo, tenga en cuenta que esto no implicaría N P = U $1/n$$NP = UP$ tenga en : nuestra lista de fórmulas de salida puede tener muchas fórmulas satisfactoriamente únicas, y tal vez algunas con muchas asignaciones satisfactorias, y parece inútil tratar de definir un cálculo de aceptación única sobre tal lista.

Incluso si de alguna manera pudiéramos dar una reducción de la lista en la que una satisfactoria siempre inducía una lista F ′ 1 , ... , F ′ t donde la mayoría de las F ′ j 's son exclusivamente satisfactorias, no hay una forma clara de convertir eso en Una reducción singleton determinista para el aislamiento. La verdadera dificultad subyacente es que no conocemos ninguna "operación de mayoría aproximada para fórmulas satisfactoriamente únicas", es decir, una reducción R ( F ′ 1 , ... , F ′ t cuyo resultado es únicamente satisfactoria si la mayoría$F$$F'_1, \ldots, F'_t$$F'_j$$R(F'_1, \ldots, F'_t)$ 's son únicamente satisfactorios e insatisfactorios si la mayoría de F ′ $F'_j$$F'_j$ ' s son insatisfactorias. Esto también parece un fenómeno general: las reducciones generan objetos más complejos que los algoritmos de decisión, y las propiedades de estos objetos son más difíciles de verificar, por lo que es más difícil combinar muchos de estos objetos en un solo objeto que hereda alguna propiedad de la mayoría.

Para el caso Valiant-Vazirani, ni siquiera parece probable bajo supuestos plausibles de desrandomización que podamos obtener , es decir, reducir de manera determinista fórmulas satisfactorias a fórmulas satisfactorias con ≤ poli ( n ) soluciones Intuitivamente, esto se debe al hecho de que el procedimiento de aislamiento no tiene ni idea del tamaño aproximado del conjunto de solución de la fórmula F que se le da.$NP = FewP$$\leq$$(n)$$F$

En el mundo oráculo, es fácil dar ejemplos donde la aleatoriedad nos da mucho más poder. Considere, por ejemplo, el problema de encontrar un cero de una función booleana equilibrada. Un algoritmo aleatorio logra que el uso de consultas con probabilidad de éxito constante, mientras que cualquier algoritmo determinista requiere al menos n /$O(1)$$n/2$ consultas.

Aquí hay otra situación en la que se sospecha que la aleatorización ayuda. Supongamos que queremos maximizar una función submodular monótona sobre una restricción matroide. Hay dos algoritmos diferentes que dan una aproximación , y esto es óptimo en este modelo por un resultado de Vondrák. Ambos algoritmos necesitan calcular una función de la forma E x ∼ X f ( x ) , donde $1-1/e$$\mathbb{E}_{x \sim X} f(x)$$X$es una distribución con soporte exponencial. Calcular esta función exactamente es demasiado costoso, pero se puede aproximar por muestreo y el resultado es un algoritmo aleatorio. En contraste, el algoritmo determinista más conocido, el algoritmo codicioso, da un aproximación.$1/2$

Una situación similar ocurre en la maximización submodular sin restricciones (aquí la función no es necesariamente monótona). El algoritmo de avance reciente da una óptima aproximación, pero su versión determinista da sólo 1 / 3 aproximación. Aquí la aleatorización se manifiesta exactamente de la misma manera que en el caso monótono o (en una versión diferente del algoritmo) haciendo algunas elecciones aleatorias en el camino.$1/2$$1/3$

Uno de los autores de estas últimas conjeturas de papel que es el mejor que un algoritmo determinista puede lograr, y de manera similar podemos conjeturar que 1 /$1/3$$1/2$ es el mejor que se puede lograr en el problema anterior. Si estas conjeturas son ciertas, entonces esta es una situación muy natural en la que la aleatorización probablemente sea de ayuda.

Recientemente, Dobzinski y Vondrák mostraron cómo transformar los límites inferiores del oráculo de valor (para algoritmos aleatorios) en resultados de dureza, condicional a NP diferente de RP (el ingrediente clave es la decodificación de listas). Debemos mencionar que la transformación se basa en el método específico utilizado para probar los límites inferiores del oráculo. Quizás sea cierto que los límites inferiores del oráculo de valor determinista también se traducen en resultados de dureza.

Una razón por la que puede parecerle extraño, que parece que creemos que hay más poder aparente (o conjeturado) en las reducciones aleatorias de a U P que la comparable de B P P a $\mathsf{NP}$$\mathsf{UP}$$\mathsf{BPP}$$\mathsf P$ , es porque usted puede ser Está tentado a pensar en la aleatoriedad como algo que es poderoso (o no poderoso) independientemente de la "máquina" a la que se agrega (si caricaturizamos estas clases de complejidad como clases que surgen de los modelos de máquina).

Y, sin embargo, existen estas reducciones de poder diferente. De hecho, un recurso computacional como la aleatoriedad no necesariamente tiene una cantidad fija de potencia computacional, que es "significativa" o "no significativa".

Podemos considerar cualquier clase de complejidad que sea baja para sí misma, por ejemplo, , P , B P P , B Q P , ⊕ P o P S P A C E si nos limitamos a restricciones prácticas en los recursos ( por ejemplo,  realizables físicamente y capaz de producir respuestas en tiempo polinómico de bajo grado para problemas de interés), pero a diferencia de clases como N P , para las cuales no tenemos idea de cómo una máquina no determinista podría producir la respuesta a otro problema en N $\mathsf L$$\mathsf P$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{\oplus P}$$\mathsf{PSPACE}$ , es susceptible de un tipo de modelo de máquina en el que la máquina siempre tiene un estado bien definido sobre el que puede hacer preguntas en cualquier momento, al tiempo que permite que el cálculo continúe más allá de la pregunta que hace: en esencia, exactamente que la máquina puede simular un algoritmo como una subrutina para otro. La máquina que realiza el cálculo puede no ser particularmente realista.$\mathsf{NP}$$\mathsf{NP}$ y usar la respuesta de cualquier manera, aparte de las reducciones conjuntas y disyuntivas de la tabla de verdad disyuntiva, imaginando que una clase está encarnada por una máquina con un estado bien definido en el que podemos preguntar No nos lleve por mal camino.

Si tomamos esta posición, podemos preguntar qué sucede si proporcionamos a estos modelos computacionales con facilidades adicionales tales como aleatoriedad o no determinismo. (Estas instalaciones adicionales no necesariamente conservan la propiedad de ser interpretables por un modelo de máquina, especialmente en el caso del no determinismo, pero dan lugar a clases 'nuevas'). Si esta instalación adicional le da más poder al modelo, da lugar a para una clase C , esto es en efecto equivalente a decir que hay una reducción de C a M usando esa facilidad, por ejemplo ,  una reducción aleatoria en el caso de aleatoriedad.$\mathsf M$$\mathsf C$$\mathsf C$$\mathsf M$

La razón por la que estoy describiendo esto en términos de clases que son bajas para ellos mismos es que si tomamos en serio que son "posibles modelos de computación en otro mundo", su pregunta sobre las reducciones aleatorias corresponde al hecho de que parece que la aleatoriedad aumenta drásticamente el poder de algunos modelos pero no de otros .

En lugar de reducciones aleatorias de a U P , podemos observar que hay una reducción aleatoria de todo P H a la clase B P ⋅ ⊕ P , que se obtiene si agrega aleatoriedad de error acotado a ⊕ P - por Teorema de Toda. Y su pregunta puede plantearse como: ¿por qué sucede esto ? ¿Por qué algunas máquinas deberían ganar tanto de la aleatoriedad y otras tan poco? En el caso de P H ⊆ B P ⋅ ⊕ P , parece que el no determinismo del módulo-2 implica la definición de$\mathsf{NP}$$\mathsf{UP}$$\mathsf{PH}$$\mathsf{BP\cdot\oplus P}$$\mathsf{\oplus P}$$\mathsf{PH} \subseteq \mathsf{BP\cdot\oplus P}$$\mathsf{\oplus P}$$\mathsf{\oplus P}$

$\mathsf{BPP} = \mathsf{P}$$\mathsf{BPP} \subseteq \Sigma^{\mathsf p}_2 \cap \Delta^{\mathsf p}_2$$\mathsf{NP}$ and $\mathsf{coNP}$. (Of course, it's difficult to prove anything nontrivial in complexity theory; but that again is just the statement that these different sorts of resources are difficult to compare on a scale!)

There is no strong argument that I can give to defend why this should be the case, other than to observe that so far it simply is the case; and that if you think that $\mathsf{PH}$ doesn't collapse, is different from $\mathsf{\oplus P}$, and that $\mathsf{BPP} \approx \mathsf{P}$, then you should consider the possibility that facilities such as randomness and nondeterminism can have powers which are not easily comparable to one another, and which can synergize or catalyse one another to give computational power that neither one would plausibly have on its own. The hypothesis that $\mathsf{BPP} = \mathsf{P}$ is not that "randomness has no power", but that randomness alone (or rather, supplemented only by polynomial time computation and provided to an otherwise deterministic computational model) is not powerful. But this does not mean that there can be no power in randomness, which may be catalysed by other computational resources.