¿Cuántas negaciones necesitamos para calcular funciones monótonas?

14

Razborov demostró que la coincidencia de la función monótona no está en mP . Pero, ¿podemos calcular la correspondencia utilizando un circuito de tamaño polinómico con algunas negaciones? ¿Hay un circuito P / poly con negaciones que calcule la coincidencia? ¿Cuál es la compensación entre el número de negaciones y el tamaño de la coincidencia?O(nϵ)

Anónimo
fuente

Respuestas:

21

Markov demostró que cualquier función de n entradas se puede calcular con solo log(n+1) negaciones. Fisher describió una versión constructiva eficiente. Vea también una exposición del resultado del blog GLL .

Más precisamente:

Teorema: supongamos que se calcula mediante un circuito C con puertas g , luego también se calcula mediante un circuito C con 2 g + O ( n 2 log 2 n ) puertas y log ( n + 1 ) negaciones.f:{0,1}n{0,1}mCgC2g+O(n2log2n)log(n+1)

La idea principal es agregar para cada cable en C un cable paralelo w ' en C que siempre lleva el complemento de w . El caso base es para los cables de entrada: Fisher describe cómo construir un circuito de inversión I ( x ) = ¯ x con puertas O ( n 2 log 2 n ) y solo log ( n + 1 ) negaciones. Para las puertas Y del circuito C , podemos aumentar unwCwCwI(x)=x¯O(n2log2n)log(n+1)C con a = b c , y lo mismo para las puertas OR. Las puertas NOT en C no cuestan nada, solo intercambiamos los roles de w y w ' aguas abajo de la puerta NOT. De esta manera, todo el circuito además del subcircuito inversor es monótono.a=bca=bcCww

AA Markov. Sobre la complejidad de inversión de un sistema de funciones. J. ACM , 5 (4): 331–334, 1958.

MJ Fischer. La complejidad de las redes de negación limitada: una breve encuesta. En teoría de autómatas y lenguajes formales , 71–82, 1975

mikero
fuente
¿Es un circuito P / poli?
Anónimo el
2
Sí, el tamaño del circuito va de a 2 g + O ( n 2 log 2 n ) donde n es el número de entradas. He ampliado la respuesta para incluir una declaración más precisa del resultado y hacerlo más autónomo. g2g+O(n2log2n)n
mikero
44
Y algunas funciones monótonas explícitas (de salida múltiple) en P / poly requieren al menos las negaciones para permanecer en P / poly. lognO(loglogn)
Stasys
2
Para esta línea de preguntas (poder de las negaciones en circuitos / fórmulas / etc.), lo siguiente puede ser relevante: eccc.hpi-web.de/report/2014/144 , eprint.iacr.org/2014/902 y eccc. hpi-web.de/report/2015/026 .
Clemente C.
2
es suficiente condimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-31.html. 2g+O(nlogn)
Emil Jeřábek apoya a Monica el
1

Cómo calcular la inversión de bits usando n negaciones2n1n

Deje que los bits se ordenen en orden decreciente, es decir, i < j implica x ix j . Esto se puede lograr mediante una red de clasificación monótona como la red de clasificación Ajtai – Komlós – Szemerédi.x0,,x2n1i<jxixj

Definimos el circuito de inversión para bits I n ( x ) inductivamente: Para el caso base tenemos n = 1 e I 1 0 ( x ) : = ¬ x 0 . Sea m = 2 n - 1 . Reducimos I n (para 2 m + 1 ) bits a una I n - 1 puerta (para m2n1In(x)n=1I01(x):=¬x0m=2n1In2m+1In1mbits) y una puerta de negación con y puertas. Usamos la negación para calcular ¬ x m . Para i < m let y i : = ( x i¬ x m ) x m + i . Usamos I n - 1 para invertir y . Ahora podemos definir I n de la siguiente manera:¬xmi<myi:=(xi¬xm)xm+iIn1yIn

Iin:={Iin1(y)¬xmi<m¬xmi=mIin1(y)¬xmi<m

Es fácil verificar que esto invierte considerando los posibles valores de x ny utilizando el hecho de que x está disminuyendo.xxnx

De Michael J. Fischer, La complejidad de las redes de negación limitada: una breve encuesta, 1975.

Anónimo
fuente