¿Es posible usar restricciones aleatorias para obtener un límite inferior para

Hay varios conocidos $\mathsf{AC^0}$ de límite inferior de tamaño de circuito basados en restricciones aleatorias y el Lema de conmutación .

¿Podemos desarrollar un resultado de Lema de conmutación para probar un tamaño de límite inferior para circuitos $\mathsf{TC^0}$ (similar a las pruebas de límite inferior para $\mathsf{AC^0}$ )?

¿O hay algún obstáculo inherente al uso de este enfoque para probar límites inferiores de ? $\mathsf{TC^0}$

¿Los resultados de la barrera, como las Pruebas naturales, dicen algo sobre el uso de técnicas similares a Switching Lemma para probar límites inferiores de ? $\mathsf{TC^0}$

cc.complexity-theory circuit-complexity lower-bounds boolean-functions Jeigh
fuente

¿Está familiarizado con la prueba de cambio de lema para

A C^{0}

$\mathsf{AC^0}$

Kaveh

Leí el capítulo de límites inferiores del circuito del libro de texto de Arora. En primer lugar, transforme cualquier traje de falda de profundidad constante en un circuito sin puertas NO con capas AND-OR entrelazadas, y en segundo lugar, usando el interruptor Switching Lemma en estas dos capas, finalmente obtenemos un circuito superior y el segundo nivel es las mismas puertas AND (u OR) así podemos privar al cicuit de una capa, limitando la profundidad del circuito.

Jeigh

Sin embargo, no es más simple que el caso booleano observar la salida de una puerta cuando fijamos varios valores de entradas (en el caso booleano arreglamos las entradas de raíz cuadrada n). La compuerta AND y la compuerta OR es una versión extrema de las compuertas de umbral y es muy fácil observar la influencia de las restricciones.

Jeigh

La idea detrás de la técnica de restricciones aleatorias es que un

golpeado por una restricción aleatoria se vuelve más simple (de hecho constante) con probabilidad distinta de cero mientras se mantienen suficientes variables libres. A diferencia de las puertas

, una sola

A C^{0}

$\mathsf{AC^0}$

\land

$\land$

\lor

$\lor$

puerta golpeada por una restricción aleatoria todavía calcularía un

\mod p

$\mod p$

gate en entradas de menor tamaño y no será más simple.

\mod p

$\mod p$

Kaveh

Tenga en cuenta también que las restricciones aleatorias y el Lema de conmutación son uno de los principales ejemplos de pruebas naturales. En cualquier caso, es de esperar que un experto en complejidad de circuitos publique una respuesta más completa. PD: Me tomé la libertad de volver a escribir la pregunta, siéntase libre de retroceder si no le gusta mi edición.

Kaveh

Respuestas:

En realidad, es posible hacer uso de restricciones aleatorias para probar límites inferiores para circuitos de umbral.

En particular en las compensaciones de tamaño-profundidad de papel para circuitos de umbral compensaciones de , Impagliazzo, Paturi y Saks usan restricciones aleatorias para probar un límite inferior del superliner (en el número de cables) para circuitos de umbral de profundidad constante que calculan la función de paridad.

Con respecto a la prueba de límites inferiores superpolinomiales para circuitos entonces sí, el concepto de prueba natural es relevante ya que hay construcciones de generadores de funciones pseudoaleatorios en . $\mathsf{TC}^0$ $\mathsf{TC}^0$

Kristoffer Arnsfelt Hansen
fuente

Véase también el artículo reciente de Daniel Kane y Ryan Williams, Super-Linear Gate y Super-Quadratic Wire Lower Bounds para los circuitos de umbral de profundidad-2 y profundidad-3 (STOC 2016).

Ryan describe el artículo de la siguiente manera (la siguiente descripción está tomada de su página de inicio):

Otorgamos una función explícita en para la cual la mayoría de los circuitos de umbral lineal de profundidad dos (con pesos ilimitados) necesitan aproximadamente puertas cables, simultáneamente. También mostramos que la función de Andreev (computable por un circuito mayoritario de profundidad tres de tamaño ) requiere que se calcule aproximadamente el mismo límite inferior de puerta y cable con circuitos de umbral lineal de profundidad dos. Una herramienta clave es el Lema de Littlewood-Offord, que utilizamos para analizar el efecto de las restricciones aleatorias en las entradas de los circuitos de umbral de baja profundidad. $\mathsf{PP}$ $n^{1.5}$ $n^{2.5}$ $O(n)$

Yuval Filmus
fuente