Teorema de Adleman sobre infinitas semirrelaciones?

13

Adleman ha demostrado en 1978 que BPPP/poly : si una función booleana f de n variables puede calcularse mediante un circuito booleano probabilístico de tamaño M , entonces f también puede calcularse mediante un circuito booleano determinista de tamaño polinomio en M y n ; en realidad, de tamaño O(nM) .

Pregunta general: ¿Sobre qué otros semirrelaciones (además de booleanas) tiene BPPP/poly ?

Para ser un poco más específico, un circuito probabilístico C sobre un semiring (S,+,,0,1) utiliza sus operaciones de "suma" (+) y "multiplicación" () como puertas. Las entradas son variables de entrada x1,,xn y, posiblemente, algún número de variables aleatorias adicionales, que toman los valores 0 y 1 de forma independiente con una probabilidad de 1/2 ; aquí y 1 son, respectivamente, las identidades aditiva y multiplicativa del semiring. Tal circuito de un C calculauna función dada f : S nS si para cada x S n , P r [ C ( x ) = f ( x ) ] 2 / 3 . 01C f:SnSxSnPr[C(x)=f(x)]2/3

La función de votación de m variables es una función parcial cuyo valor es y si el elemento y aparece más de m / 2 veces entre los y 1 , ... , y m , y no está definido , si no existe tal elemento y . Una aplicación simple de los límites de Chernoff y union produce lo siguiente.Maj(y1,,ym)myym/2y1,,ymy

Truco mayoritario: si un circuito probabilístico calcula una función f : S nS en un conjunto finito X S n , entonces hay m = O ( log | X | ) realizaciones C 1 , ... , C m de C de tal manera que f ( x ) = M a j ( C 1 ( x ) , Cf:SnSXSnm=O(log|X|)C1,,CmC se mantiene para todo x X . f(x)=Maj(C1(x),,Cm(x))xX

Durante el semiseño booleano, la función de votación es la función mayoritaria y tiene circuitos pequeños (incluso monótonos). Entonces, el teorema de Adleman sigue tomando X = { 0 , 1 } n . MajX={0,1}n

Pero, ¿qué pasa con otros semirrelaciones (especialmente infinitas)? ¿Qué pasa con el semiring aritmético (con la suma y multiplicación habitual)?(N,+,,0,1)

Pregunta 1: ¿ aferra al semirremolque aritmético? BPPP/poly

Aunque apuesto por "sí", no puedo mostrar esto.

Observación: Conozco este artículo donde los autores afirman sobre el campo real ( R , + , , 0 , 1 ) . Tratan con circuitos aritméticos no monótonos y también llegan (en el Teorema 4) a circuitos con la función de votación M a j como puerta de salida. Pero, ¿cómo simular esta puerta M a j mediante un circuito aritmético (sea monótono o no)? Es decir, ¿cómo obtener su Corolario 3?BPPP/poly(R,+,,0,1)MajMaj

En realidad, el siguiente argumento simple que me contó Sergey Gashkov (de la Universidad de Moscú) parece mostrar que esto es imposible (al menos para los circuitos capaces de calcular solo polinomios ). Supongamos que podemos expresar como un polinomio f ( x , y , z ) = a x + b y + c z + h ( x , y , z ) . Entonces f (Maj(x,y,z)f(x,y,z)=ax+by+cz+h(x,y,z) implica c = 0 , f ( x , y , x ) = x implica b = 0 , yf ( x , y , y ) = y implica a = 0 . Esto es válido porque, sobre campos de característica cero, la igualdad de funciones polinómicas significa igualdad de coeficientes. Tenga en cuenta que en la Pregunta 1, el rango de los circuitos probabilísticos y, por lo tanto, el dominio de la Mf(x,x,z)=xc=0f(x,y,x)=xb=0f(x,y,y)=ya=0 puerta j esinfinita. Por lo tanto, tengo la impresión de que el trabajo vinculado solo trata con funciones de cálculo de circuitos aritméticos f : R nY con rangos finitos pequeños Y , como Y = { 0 , 1 } . Entonces M a j : Y mY es realmente fácil de calcular mediante un circuito aritmético. Pero, ¿y si Y = R ? Majf:RnYYY={0,1}Maj:YmYY=R


Corrección [6.03.2017]: Pascal Koiran (uno de los autores de este artículo) me señaló que su modelo es más poderoso que solo los circuitos aritméticos: permiten puertas de señal (con salida o 1 dependiendo de si la entrada es negativa de no). Entonces, la función de votación Maj se puede simular en este modelo, y retomo mi "confusión".01


En el contexto de la programación dinámica, es especialmente interesante la misma pregunta para semirreferencias tropicales min-plus y max-plus y ( N{ - } , max , + , - , 0 ) .(N{+},min,+,+,0)(N{},max,+,,0)

Pregunta 2: ¿El control sobre semirings tropicales? BPPP/poly

Celebrada en estos dos semirrelaciones, esto significaría que la aleatoriedad no puede acelerar los llamados algoritmos de programación dinámica "puros". Estos algoritmos solo usan operaciones Min / Max y Sum en sus recursiones; Bellman-Ford, Floyd-Warshall, Held-Karp y muchos otros algoritmos DP prominentes son puros. BPPP/poly

Hasta ahora, solo puedo responder la pregunta 2 (afirmativamente) en el escenario de error unilateral , cuando adicionalmente requerimos durante el min-plus semiring (minimización), o P r [ C ( x ) > f ( x ) ] = 0Pr[C(x)<f(x)]=0Pr[C(x)>f(x)]=0sobre el semi-max-plus (maximización). Es decir, ahora requerimos que el circuito tropical aleatorizado nunca pueda producir un valor mejor que el óptimo; sin embargo, puede equivocarse al dar algunos valores peores que óptimos. Sin embargo, mis preguntas están bajo el escenario de error de dos lados .


PD [agregado el 27.02.2017]: Aquí está mi intento de responder la Pregunta 1 (afirmativamente). La idea es combinar una versión más simple del "Nullstellensatz combinatorio" con una estimación del problema de Zarankiewicz para hipergraps n-partitos, debido a Erdos y Spencer. Módulo este último resultado, todo el argumento es elemental.

Tenga en cuenta que la pregunta 2 aún permanece abierta: el "ingenuo Nullstellensatz" (al menos en la forma que usé) no se mantiene en semirremolques tropicales.

Stasys
fuente
nit: BPP es una clase uniforme definida usando PTMs no circuitos.
Kaveh
@Kaveh: sí, en este sentido, el resultado de Adleman es incluso un poco más fuerte, incluso para BPP / poly.
Stasys
No veo cómo el argumento simple muestra imposibilidad ... parece mostrar que los coeficientes de los monomios x, y y z deben ser cero ... ¿qué me estoy perdiendo? Además, si un polinomio no puede calcular Maj, ¿de qué otra manera puedes representar un cálculo en un semiring? (¿Qué más, además de un polinomio sobre el semirremolque?) Intuitivamente, sobre un dominio infinito, cada restricción sobre algunos y (haciendo cumplir que en> m / 2 y's debe generar y) parece "independiente" de los otros (no implica un subconjunto de restricciones otro) por lo que parece que ningún polinomio "finito" podría satisfacer las infinitas restricciones independientes.
Ryan Williams
@ Ryan: sí, esto solo muestra f = Maj implica h = Maj. Pero h tiene grado> 1, entonces h (x, x, z) = x es imposible. Y tiene razón: los circuitos sobre semirremolques no pueden computar nada más como polinomios. Por lo tanto, no pueden calcular Maj. Pero los autores de ese artículo tratan con circuitos {+, x, -, /}, con todas las operaciones de campo permitidas. ¿Quizás entonces Maj pueda ser calculado de alguna manera? (Sin embargo, no veo cómo). Por cierto, en lugar de tratar de simular Maj en sí, uno podría responder Q1 y Q2 mostrando que una Maj-gate no puede disminuir sustancialmente el tamaño del circuito (lo cual es bastante plausible).
Stasys
@ Ryan: PS Igor Sergeev observó que Maj "podría" ser probable computable sobre (R, +, x, -, /). Por ejemplo, Maj (x, y, z) es computable por f (x, y, z) = (xy + xz-2yz) / (2x-yz) para todas las entradas con | {x, y, z} | = 2. Tenga en cuenta que el argumento simple anterior implica que, ya en tales entradas, esto no puede hacerse sobre (R, +, x, -). Entonces, la división puede ayudar. Pero enfrentamos la división por 0 problema ...
Stasys

Respuestas:

3

Esta es solo una respuesta parcial a su pregunta general (no estoy seguro de cuál sería una formulación totalmente general), pero sugiere que trabajar sobre semirrelaciones infinitas suficientemente agradables al tiempo que restringe la aleatoriedad a un dominio finito en realidad podría trivializar la pregunta de si El teorema de Adleman es válido.

CfxrC(x,r)=f(x)rxC(x,r)=f(x)Cn, and so must be all of Cn, or else a subset of measure zero. If all of these sets were to have measure zero, then, because there are only finitely many r's in consideration, the set of x where r:C(x,r)=f(x) would also have measure zero. On the other hand, the assumption that C computes f implies this that set must be all of Cn, so it cannot have measure zero.

Andrew Morgan
fuente
Interesting. More generally, a probabilistic circuit of size M is some random variable C taking its values in the set of all circuits (of that type) with at most M gates. [B.t.w. that paper of Cucker at al. allows C be arbitrarily distributed. The "majority trick" stil works.] Can I conclude from your argument that, if the range of C is finite, then Adleman's theorem is trivial when Zarinski-closed subsets are either trivial (sets themselves) or have zero measure? Have we this - "all or nothing" - effect in tropical semirings? (I am mainly interested in them.)
Stasys
No sé cómo o si el argumento se generalizaría a otros semirrecursos, lo siento. Una cosa principal que falta (para mí) es la intuición geométrica similar a cómo "polinomios que no están de acuerdo" se traduce en "subconjuntos de medida cero deCnorte". Para los semirremolques tropicales en particular, las operaciones parecen tan diferentes de los polinomios ordinarios que es difícil incluso adivinar cuál debería ser la adaptación adecuada.
Andrew Morgan