Preguntas etiquetadas con circuit-complexity

La complejidad del circuito es el estudio de los circuitos limitados por recursos y las funciones calculadas por dichos circuitos.

31
¿Está

Pensé en compartir esta pregunta, ya que podría ser interesante para otros usuarios aquí. Suponga que una función que está en una clase uniforme (como ) también está en una pequeña clase no uniforme (como A C 0 / p o l y , es decir, no uniforme A C 0 ), ¿esto implica que la función está contenida...

29
Coeficientes de Fourier Funciones booleanas descritas por circuitos de profundidad acotada con compuertas AND OR y XOR

Sea fff una función booleana y pensemos en f como una función desde {−1,1}n{−1,1}n\{-1,1\}^n hasta . En este lenguaje, la expansión de Fourier de f es simplemente la expansión de f en términos de monomios libres cuadrados. (Estos monomios forman una base para el espacio de funciones reales en . La...

23
¿Es

En la encuesta "Circuitos cuánticos de pequeña profundidad" de D. Bera, F. Green y S. Homer (p. 36 de ACM SIGACT News, junio de 2007 vol. 38, no. 2) , leí la siguiente oración: La versión clásica de (en la que las compuertas A N D y O R tienen como máximo un despliegue constante) es...

21
¿

¿Existe alguna hipótesis plausible de complejidad / criptografía que descarte la posibilidad de que los circuitos de tamaño polinomial tengan circuitos de tamaño subexponencial (es decir, con ϵ < 1 ) de profundidad limitada ( d = O ( 1 ) )?2O ( nϵ)2O(nϵ)2^{O(n^\epsilon)}ϵ <...