Mi pregunta es acerca de la teoría del modelo finito / complejidad descriptiva, por lo que significará "primer orden sobre palabras binarias finitas, usando predicados Rs y un predicado unario P verdadero en la posición del 1 en la palabra".FO(R)FO(R)FO(R) Me gustaría saber, ¿hay alguna...
El algoritmo de Berkowitz proporciona un circuito de tamaño polinómico con profundidad logarítmica para determinar una matriz cuadrada utilizando potencias matriciales. El algoritmo utiliza implícitamente la cancelación. ¿Es esencial la cancelación para lograr un circuito de tamaño polinómico con...
Deje para , con la promesa de que (donde la suma ha terminado ). Entonces, ¿cuál es la complejidad de determinar si ?xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\}i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\}ZZ\mathbb{Z}x=1x=1x = 1 Observe que...
¿Cuál es el mejor resultado para el número de puertas en un circuito que multiplica dos enteros de n bits? El método obvio genera puertas . Hay mejores enfoques con puertas y .θ ( n2)θ(norte2)\theta(n^2)θ ( n logn logIniciar sesiónn )θ(norteIniciar sesiónnorteIniciar sesiónIniciar...
Digamos que tenemos una función booleana y aplicamos restricción aleatoria δ en f . Además, supongamos que el árbol de decisión T que calcula f se reduce al tamaño O ( 1 ) como resultado de la restricción aleatoria. ¿Esto implica que f tiene una influencia total muy baja?F: { - 1 , 1 }norte→ { - 1...
¿Alguien ha explorado cuál es la complejidad del circuito de los problemas de decisión clásicos como Primes o Graph-Isomorphism para un tamaño de entrada pequeño ?NNN Si bien la mayoría de la gente está interesada en cómo va la escala según , creo que también sería interesante ver cómo crece esto...
Creo que las respuestas a esta pregunta dan clases tales que para todos los polinomios , hay un problema en la clase que no tiene circuitos de tamaño . Sin embargo, estoy preguntando sobre el tamaño del circuito .p ( n ) ωpppp(n)p(n)p(n)ω(n)ω(n)\omega \hspace{.02
Sea una clase de complejidad y sea la contraparte aleatoria de definida de la misma manera que se define con respecto aCC\mathcal{C}BP-CBP-C\textrm{BP-}\mathcal{C}CC\mathcal{C}BPPBPP\textrm{BPP}PP\textrm{P} . Más formalmente, proporcionamos polinómicamente muchos bits aleatorios y aceptamos una...
What is Razborov's method of approximations? Can someone give a high-level overview and the intuition behind
Tengo curiosidad acerca de las formas en que ha visto que la falta de uniformidad es útil en el cálculo. Una forma es la aleatoriedad, como en , y otra son las tablas de búsqueda que se utilizan para mostrar que todos los idiomas tienen circuitos no uniformes.B PPAGS⊆ P/ polysiPAGSPAGS⊆PAGS/...
Este resultado de Tavenas, Koiran y otros muestran que cualquier polinomio calculado por un circuito de tamaño sss se calcula por un circuito homogéneo de profundidad 4 de tamaño sd√sds^{\sqrt{d}} . ¿Hay resultados similares para los circuitos booleanos o sabemos por qué tal cosa no es posible?...
Hace unos años, tomé una clase sobre teoría de la complejidad de Steven Rudich, y recuerdo que él dio una conferencia interesante que conecta las pruebas estadísticas (¡como se encuentra en los departamentos de estadística!) Con la complejidad del circuito. Lo recuerdo afirmando algo vagamente...
esta es una reescritura de otra pregunta reciente mía [1] que no se dijo bien (tenía una simplificación semi obvia, mea culpa) pero creo que todavía hay una pregunta no trivial en el fondo. He visto problemas similares en la literatura pero no este en particular. lo escribirá en términos de...
No es difícil mostrar que ordenar una matriz de números es difícil para . Si la entrada es una matriz de 1s y 0s, entonces es esencialmente la función C o u n t (dados n bits, genera el número de 1s en binario) ya que C o u n t está completo para T C 0 y es posible para convertir números unarios en...
¿Existe una prueba alternativa o una exposición del resultado de Grigoriev y Karpinski (STOC 1998, doi: 10.1145 / 276698.276872 ) en los límites inferiores exponenciales para circuitos aritméticos de Profundidad 3 que calculan sobre un campo finito fijo?DETn×nDETn×n\mathsf{DET}_{n\times n} No pude...
Estaba leyendo On Bulls * t de Harry Frankfurt , un ensayo filosófico de 1986 sobre esta noción borrosa entre verdad y falsedad. Este no es un ejercicio gratuito. Esto puede tener aplicaciones para la informática, ya que siempre estamos conectando conjuntos de datos entre sí . Algunas de estas...
La complejidad del espacio monótono de un lenguaje se puede definir en términos de redes de conmutación monótonas (véase, por ejemplo, "Límites inferiores a mayúsculas y minúsculas para redes de conmutación monótonas" de Filmus et al.). Esta noción está vinculada a la jerarquía monótona N C y puede...
En [1] se afirma que "Sigue siendo una pregunta abierta si cada función en tiene circuitos (aunque al menos se sabe que no todas las funciones tienen circuitos uniformes DLogTime )".T C 0 # P T C 0#P#P\#PTC0TC0TC^0#P#P\#PTC0TC0TC^0 TC0TC0TC^0 circuitos generados por las funciones DLogTime no...
Como se muestra en el documento "Circuitos monótonos para la función mayoritaria", es posible construir un circuito booleano monótono para la función mayoritaria en n variables con tamaño O (n ^ 3) y profundidad 5.3 log (n) + O (1). http://link.springer.com/chapter/10.1007/11830924_38 Mi...
Savický y Woods (El número de funciones booleanas calculadas por fórmulas de un tamaño dado) demuestran el siguiente resultado. Teorema [SW98]: Para cada constante , casi todas las funciones booleanas con complejidad de fórmula como máximo n k tienen complejidad de circuito al menos n k / k...