Ancho de árbol mínimo del circuito para MAYORÍA

¿Cuál es el ancho de árbol mínimo de un circuito sobre $\{\wedge,\vee,\neg\}$ para calcular MAJ?

Aquí MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ produce 1 si al menos la mitad de sus entradas son $1$ .

Solo me importa el tamaño del circuito (debe ser polinomial) y que una entrada debe leerse solo una vez, aunque el abanico de una puerta de entrada puede ser arbitrario (esto afecta de manera crucial el ancho del árbol del circuito: la ramificación los programas obtenidos del teorema de Barrington del MAJ $\in$ $\mathsf{NC}^1$ , interpretados como circuitos oblicuos, no ayudan). Y, por supuesto, el ancho del árbol es lo más crucial. No me importa la profundidad ni ningún otro parámetro.

Algunos de los circuitos comunes para MAJ incluyen:

¿Circuitos de árbol de Wallace (por ejemplo, el Teorema 8.9 aquí ) que usan el truco de 3 a 2 para colocar MAJ en $\mathsf{NC}^1$ ?
Circuitos monótonos Valiant $\mathsf{NC}^1$ para MAJ (por ejemplo, Teorema 4 aquí )
$\log^{O(1)}{n}$ red de clasificación de profundidad, como laclasificación deBatcher
Red de clasificación AKS

¿Alguno de ellos tiene un ancho de árbol acotado o incluso pollogarítmico?

O de hecho

¿Hay razones para creer que no hay circuitos acotados de ancho de árbol para MAJ?

Tenga en cuenta que cada función calculada por un circuito de ancho de árbol acotado puede calcularse por un circuito incluso cuando no hay una estipulación de lectura única a través de JansenSarma . Por lo tanto, la inverosimilitud de una familia de circuitos de este tipo indicaría que este límite puede reforzarse aún más en el caso de los circuitos de lectura única. $\mathsf{NC}^1$

reference-request complexity-classes circuit-complexity treewidth SamiD
fuente

¿Por qué esto no es trivial para cualquier

? Hasta donde puedo ver, las fórmulas (es decir, los árboles) tienen un ancho de árbol

, ¿o me falta algo?

{N C}^{1}

$\mathrm{NC}^1$

1

$1$

Emil Jeřábek

Creo que OP identifica todas las hojas del árbol de fórmulas que corresponden a la misma variable, lo que crea ciclos.

Sasho Nikolov

Se puede implementar un circuito para la mayoría en el ancho de árbol O (log n). El circuito simplemente simula un algoritmo en línea que lee un bit de entrada a la vez y agrega 1 a un número con bits O (log n) si y solo si la entrada es 1. Tenga en cuenta que la profundidad del circuito es O (n). Consulte la figura 1 de ( arxiv.org/pdf/1404.5565v1.pdf ). Un circuito de pequeña profundidad no necesariamente tiene un ancho de árbol pequeño porque, como señaló Sasho Nikolov, es necesario identificar los nodos correspondientes a la misma variable de entrada.

Mateus de Oliveira Oliveira

@MateusdeOliveiraOliveira La construcción que señala es agradable y simple y es casi lo que necesito. Lo que realmente necesito es una construcción que funcione en un ancho de árbol limitado (o alguna indicación de por qué eso no es posible). Esperaré un par de días para ver si hay alguna otra respuesta; de lo contrario (si convierte su comentario en una respuesta), la aprobaré.

SamiD

@SamiD Expandí este comentario en una respuesta. No había publicado como respuesta antes porque es solo la mitad de lo que pediste.

Mateus de Oliveira Oliveira

Respuestas:

Respondiendo la mitad de la pregunta de Samir.

Deje que sea un DAG y ser dos subconjuntos de vértices de . Denotamos por el conjunto de todos los bordes en con un punto final en y otro punto final en . Si $G=(V,E)$ $V_1,V_2\subseteq V$ $G$ $E(V_1,V_2)$ $G$ $V_1$ $V_2$ $\omega = (v_1,...,v_n)$ $G$

o w (G, ω) = max_{i} | E ({v_{1}, . . ., v_{i}}, {v_{i + 1}, . . ., v_{n}} |

$\mathbf{ow}(G,\omega) = \max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$

ω

$\omega$

G

$G$

o w (G) = min_{ω} o w (G, ω),

$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$

G

$G$

G

$G$

c w (G)

$\mathbf{cw}(G)$

G

$G$ , independientemente de si el ordenamiento es topológico o no. Tenemos la siguiente secuencia de desigualdades: donde y son, respectivamente, la pathwidth y la treewidth de .

t w (G) \leq p w (G) \leq c w (G) \leq o w (G),

$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$

p w (G)

$\mathbf{pw}(G)$

t w (G)

$\mathbf{tw}(G)$

G

$G$

Afirmamos que la MAYORÍA de bits se puede calcular en el ancho en línea y, por lo tanto, en el ancho de árbol . El circuito simula un algoritmo en línea que lee un bit de entrada a la vez y agrega a un contador con bits si y solo si . Al principio, el contador se inicializa a $n$ $O(\log n)$ $O(\log n)$ $b$ $b$ $O(\log n)$ $b=1$ $0$ . Al final, el circuito acepta si y solo si el valor del contador es mayor que n / 2. Es fácil ver que las puertas de un circuito ADD que agrega una al registro de contador pueden ordenarse topológicamente de tal manera que tenga un ancho constante en línea, ya que estos circuitos solo necesitan implementar una operación de continuación. El circuito total es una secuencia de circuitos donde la salida de se conecta a la entrada de , y la salida de se conecta a la entrada de COMP. Ahora, si topológicamente el circuito total de tal manera que todas las puertas de aparezcan antes que las puertas de y todas las puertas de $C=(ADD_1,ADD_2,...,ADD_n,COMP)$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ $C$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ aparece antes de las puertas de COMP, entonces este orden topológico tiene un ancho en línea . Esta construcción se ilustra en la Figura 1 de un artículo mío para mostrar que la amplificación de probabilidad se puede hacer en ancho logarítmico en línea. $O(\log n)$

Obs: La profundidad del circuito C es . $O(n)$

Mateus de Oliveira Oliveira
fuente

Como observación lateral, hacer el mismo circuito pero como un árbol binario (con la salida en la raíz) en lugar de una ruta da un circuito con ancho de árbol O (log n) y profundidad O (log n)

daniello

Parece que una traducción directa a árboles daría profundidad O ((log n) ^ 2) ya que necesitaríamos profundidad O (log n) para cada sumador. Pero es cierto que el ancho del árbol sería O (log n).

Mateus de Oliveira Oliveira

Por supuesto que tienes razón, gracias! Parece que si las adiciones se implementan como DNF, obtenemos el ancho del árbol y la profundidad O (log n), pero el tamaño .

O (n^{3})

$O(n^3)$

daniello

Lo que representa representar al sumador como DNF es que puede aumentar potencialmente el ancho del árbol, ya que ahora cada variable se compartirá con (a primera vista polinomialmente) muchas cláusulas. Su sugerencia de reducir la profundidad a O (log n) funcionaría si puede mostrar que la suma de dos números con bits O (log n) se puede hacer en profundidad constante y ancho de árbol logarítmico.

Mateus de Oliveira Oliveira

Bueno - para cualquier función booleana en bits de entrada y bits de salida del DNF tiene profundidad , tamaño , y treewidth desde la supresión de compuertas de entrada + de salida de hojas un conjunto independiente ...

a

$a$

b

$b$

2

$2$

2^{a} + a + b

$2^a + a + b$

\leq a + b

$\leq a+b$

daniello

Respondiendo a la otra mitad de la pregunta: aquí hay un bosquejo de prueba para un límite inferior para el ancho del árbol para alguna constante . El límite es independiente del tamaño o de cualquier otro aspecto del circuito. En el resto del argumento es el circuito, es el treewidth de y es el número de puertas de entrada. $c \cdot \log n$ $c$ $C$ $t$ $C$ $n$

El primer paso es utilizar el lema separador equilibrado para gráficos de ancho de árbol acotado . Las puertas (incluidas las puertas de entrada) del circuito pueden dividirse en tres partes , y , de modo que y y contienen al menospuertas de entrada, y no hay arcos (cables) entre y . $L$ $R$ $S$ $|S| \leq t+1$ $L$ $R$ $n/3-|S|$ $L$ $R$

En el resto de la prueba, la única propiedad del circuito que usaremos es esta partición, por lo que la prueba realmente proporciona un límite inferior en el tamaño de un separador equilibrado como se anteriormente. $S$

Teniendo a mano construimos un circuito partir de siguiente manera: para cada puerta en haga dos puertas más y , y haga que y alimenten a . Para todos los cables que conducen a desde haga que entren en . Para todos los cables que conducen a desde haga que entren en . Deje $(L,S,R)$ $C'$ $C$ $g$ $S$ $g_L$ $g_R$ $g_L$ $g_R$ $g$ $g$ $L$ $g_L$ $g$ $R$ $g_R$

S^{'} = {g, g_{L}, g_{R} : g \in S} .

$S' = \{g, g_L, g_R : g \in S\}.$

Para cada una de las asignaciones a haga un circuito que dé salida a 1 si (a) la asignación a las puertas de entrada hace que salida de verdadera y (b) la asignación a las puertas de entrada establece todos los puertas de como se adivinó. Llame a estos circuitos , , para . Tenga en cuenta que el circuito naturalmente se divide en dos subcircuitos y manera que solo depende de las puertas de entrada de , solo depende de las puertas de entrada de $2^{|S'|}$ $S'$ $C'$ $S'$ $C_1$ $C_2$ $C_3 \ldots C_x$ $x \leq 8^t$ $C_i$ $C_i^L$ $C_i^R$ $C_i^L$ $L \cup S'$ $C_i^R$ $R \cup S'$ , y para cualquier asignación a las puertas de entrada que tiene que . $C_i = C_i^L \wedge C_i^R$

Dado que cada asignación a las puertas de entrada es consistente con alguna conjetura de lo que sucede en tenemos que . Por lo tanto, hemos reescrito el circuito como un OR (de fanin ) de AND (de fanin ) donde el número de puerta AND está siendo alimentado con la salida de y respectivamente. $S'$ $C' = C_1 \vee C_2 \vee C_3 \ldots \vee C_x$ $C$ $8^t$ $2$ $i$ $C_i^L$ $C_i^R$

Deje ser el conjunto de puertas AND superiores. Primero probaremos que. Esto da un simple límite inferior en . Entonces probaremos un mejor límite. $Z$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$ $t$

Suponga que, Y asumir sin pérdida de generalidad que contiene un menor número de puertas de entrada que . Entonces, tanto como contienen al menospuertas de entrada. Según el principio del palomar, hay dos números diferentes y modo que hay dos asignaciones diferentes a las puertas de entrada de , una que establece las puertas en verdadero, una que establece , de modo que los circuitos , todos lo mismo. Pero existe una asignación a las puertas de entrada en $2^{|Z|} < n/3-|S|$ $L$ $R$ $L$ $R$ $n/3-|S|$ $i$ $j$ $L$ $i$ $j$ $C_1^L$ $C_2^L \ldots C_x^L$ $R$ tal que MAJORITY emite FALSE si las puertas en están configuradas como verdaderas, y MAJORITY emite VERDADERO si las puertas en están configuradas como verdaderas. Esto es una contradicción, por lo que lo que implica que el ancho de árbol es al menos . $i$ $L$ $j$ $L$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$

Ahora mostramos un mejor límite:. Supongamos sin pérdida de generalidad que contiene un menor número de puertas de entrada que . Entonces, tanto L como R contienen al menospuertas de entrada. Considere el "todo falso" asignación a . Sea el número más pequeño de compuertas de entrada de que debe establecerse en verdadero de modo que MAJ genere VERDADERO, dado que todo está configurado en falso. $|Z| \geq n/3-|S|$ $L$ $R$ $n/3-|S|$ $L$ $r$ $R$ $L$

Desde la configuración a todas falsas y exactamente puertas de entrada de a la salida verdaderas marcas MAYORÍA tiene que haber algún tal que salidas TRUE, sin pérdida de generalidad esto se . Todas las asignaciones a con menos de puertas de entrada verdaderas deben establecer en falso. Dado que establecer puerta de entrada de en verdadero y puertas de entrada de en verdadero hace que la salida MAYORIDAD , establecer puerta de en verdadero debe hacer al menos una $L$ $r$ $R$ $1$ $i$ $C_i^L$ $C_1^L$ $R$ $r$ $C_1^R$ $1$ $L$ $r-1$ $R$ $1$ $1$ $L$ $C_i^L$ outpur verdadero para . wlog podemos suponer que . Entonces, todas las asignaciones a que establezcan como máximo las puertas de entrada en verdadero deben establecer en falso, y así sucesivamente; podemos repetir este argumento veces. Pero esto significa que, dando un límite inferior para . $i \neq 1$ $i=2$ $R$ $r-2$ $C_2^R$ $r$ $|Z| \geq r \geq n/3-|S|$ $c \cdot \log n$ $t$

[Soy consciente de que este boceto se ondula un poco en algunos lugares, pregunta si algo no está claro ...]

daniello
fuente