Se sabe que si , la jerarquía polinómica se colapsa en y .N P ⊆ P / P o l y Σ P 2 M A = A MNP⊆P/PolyNP\subseteq P/PolyΣP2\Sigma_2^{P}MA=AMMA = AM ¿Cuáles son los colapsos más fuertes que suceden si ?N E X P ⊆ P / P o l yNEXP⊆P/PolyNEXP\subseteq
P / poly es la clase de problemas de decisión que puede resolver una familia de circuitos booleanos de tamaño polinómico. Alternativamente, se puede definir como una máquina de Turing de tiempo polinómico que recibe una cadena de aviso que tiene un tamaño polinómico en n y que se basa únicamente en...
Hay varios conocidos AC0AC0\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 TC0TC0\mathsf{TC^0} (similar a las...
Sea una función booleana de n variables booleanas. Sea g ( x ) = T ϵ ( f ) ( x ) el valor esperado de f ( y ) cuando y se obtiene de x al voltear cada coordenada con probabilidad ϵ / 2 .fffnnng(x)=Tϵ(f)(x)g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f) (x)f(y)f(y)f(y)yyyxxxϵ/2ϵ/2\epsilon/2 Estoy interesado en...
¿Se sabe si el problema de evaluación del circuito está en ? ¿Qué tal (uniform )? N C 1 A L o g T i m e N C 1NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Sabemos que los circuitos de profundidad pueden evaluarse con circuitos de profundidad donde...
Sea la función mayoritaria, es decir, si y solo si . Me preguntaba si había una prueba simple del siguiente hecho (por "simple" me refiero a no confiar en el método probabilístico como Valiant 84 o en redes de clasificación; preferiblemente proporcionando una construcción explícita y directa del...
Dado un algoritmo que se ejecuta en el tiempo , podemos convertirlo en una familia de circuitos uniforme "trivial" para el mismo problema de tamaño como máximo ≈ t ( n ) log t ( n ) .t(n)t(n)t(n)≈t(n)logt(n)≈t(n)logt(n)\approx t(n)\log t(n) Por otro lado, podría ser que tengamos circuitos...
Al contar los argumentos, se puede mostrar que existen polinomios de grado n en 1 variable (es decir, algo de la forma que tienen complejidad de circuito n. Además, uno puede mostrar que un polinomio como x n requiere al menos log 2 n multiplicaciones (lo necesita solo para obtener un grado lo...
Razborov demostró que cada circuito monótono que calcula la función de coincidencia perfecta para gráficos bipartitos debe tener al menos compuertas (lo llamó "lógico permanente"). ¿Se ha demostrado un límite inferior mejor para el mismo problema desde entonces? (diga 2 n ϵ ?) Hasta donde recuerdo,...
A C0 0AC0AC^0 es la clase de circuitos de tamaño polinomial de profundidad constante con compuertas NO y compuertas AND y OR de ventilador sin límites, donde las entradas y las puertas también tienen un fanout sin límites. Ahora considere una nueva clase, que es como pero para la cual las entradas...
El peso El | x ||x||x|de una cadena binaria x ∈ { 0 , 1 }nortex∈{0,1}nx\in\{0,1\}^n es el número de unos en la cadena. ¿Qué sucede si estamos interesados en calcular una función monótona en entradas con pocas? Sabemos que decidir si un gráfico tiene una kkk -clique es difícil para los circuitos...
Considere una función calculada por un circuito booleano C con n entradas de tamaño s ( n ) = p o l y ( n ) sobre la base { X O R , A N D , N O T } (con grado 2 para la X O R , A N D puertas).FffCCCnortenns ( n ) = p o l y ( n )s(n)=poly(n)s(n) = \mathsf{poly}(n){ X O R , A N D , N O T...
Estoy considerando el lenguaje de todas las fórmulas lógicas proposicionales satisfactorias, SAT (para asegurarnos de que tenga un alfabeto finito, codificaríamos las letras proposicionales de alguna manera adecuada [editar: las respuestas señalaron que la respuesta a la pregunta puede no ser...
Sea el tamaño mínimo de un circuito aritmético (no monótono) ( + , × , - ) que calcula un polinomio multilineal dado f ( x 1 , … , x n ) = ∑ e ∈ E c e n ∏ i = 1 x e i iA ( f)A(f)A(f)( + , × , - )(+,×,−)(+,\times,-) y B ( f ) denota el tamaño mínimo de uncircuitobooleano(no monótono) ( ∨ , ∧ , ¬...
La barrera de las pruebas naturales de Razborov y Rudich establece que, bajo supuestos criptográficos creíbles, uno no puede esperar separar NP de P / poli al encontrar propiedades combinatorias de funciones que son constructivas, grandes y útiles. Hay varios resultados bien conocidos que logran...
TC0TC0\mathsf{TC^0} dTC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd La entrada del zoológico para TC0TC0\mathsf{TC^0} solo menciona la separación entre la profundidad 2 y 3. ¿También hay una referencia estándar para el hecho de que la jerarquía AC0dACd0\mathsf{AC^0_d} no...
Los idiomas Dyck se definen mediante la siguiente gramática S → S SDyck(k)Dyck(k)\mathsf{Dyck}(k) sobre el conjunto de símbolos { ( 1 , ... , ( k , ) 1 , ... , ) k } . Intuitivamente, los idiomas Dyck son los idiomas de paréntesis equilibrados de k tipos diferentes. Por ejemplo,...
¿Cuál es el ancho de árbol mínimo de un circuito sobre {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} para calcular MAJ? Aquí MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} produce 1 si al menos la mitad de sus entradas son 111 . Solo me importa el tamaño del circuito (debe ser polinomial) y...
NL⊈PNL⊈P\mathsf{NL} \nsubseteq \mathsf{P} Consideremos ahora las familias de circuitos con puertas de Oracle - por ejemplo, , donde es una clase de la complejidad del circuito que contiene logspace con acceso a Oracle a otra clase , a través de puertas de Oracle adjuntas a la base de . ¿Hay algún...
¿Qué tipo de teoremas de jerarquía existen para la profundidad del circuito? Declaraciones como g(n)∈o(f(n))g(n)∈o(f(n))g(n) \in o(f(n))f(n)∈nO(1)f(n)∈nO(1)f(n) \in n^{O(1)}SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))\mathsf{SizeDepth}(n^{O(1)}, g(n))...