Preguntas etiquetadas con circuit-complexity

¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...

Estoy interesado en una función booleana explícita con la siguiente propiedad: si es constante en algún subespacio afín de , entonces la dimensión de este subespacio es .f:0,1n→0,1f:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}fff0,1n0,1n\\{0,1\\}^no(n)o(n)o(n) No es difícil demostrar que una...

Parte del trabajo sobre la sensibilidad frente a la sensibilidad del bloque se ha dirigido a examinar funciones con un espacio lo más amplio posible entre y para resolver la conjetura de que solo es polinomialmente más grande que . ¿Qué pasa con la dirección opuesta? ¿Qué se sabe sobre las...

Un circuito booleano no determinista tiene, además de las entradas ordinarias , un conjunto de entradas "no deterministas" y = ( y 1 , ... , y m ) . Un circuito no determinista C acepta la entrada x si existe y tal que la salida del circuito 1 está activada ( x , y ) . Análogo a P / p o l yx = (...

Como es bien sabido, PARITY no se puede hacer en circuitos de profundidad constante de tamaño polivinílico, y de hecho, los circuitos const-dept requieren un número EXP de compuertas. ¿Qué pasa con los circuitos QUANTUM? a) ¿Se puede hacer PARITY con un circuito cuántico que tiene una profundidad...

El límite inferior Blum 3n−o(n)3n−o(n)3n-o(n)es el límite inferior del circuito más conocido sobre la base completa de una función explícita f:{0,1}n→{0,1}f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\} , cf. La respuesta de Jukna a esta pregunta para obtener resultados relacionados. ¿Cuáles son los...

Se sabe que el tamaño mínimo de los U_2 que calculan la función de paridad es exactamente igual a . La prueba de límite inferior se basa en el método de eliminación de puerta.U2U2U_23(n−1)3(n−1)3(n-1) Recientemente, noté que el método de eliminación de compuerta funciona bien también para U_2 no...

La complejidad del circuito de profundidad limitada es una de las principales áreas de investigación dentro de la teoría de la complejidad del circuito. Este tema tiene su origen en resultados como "la función de paridad no está en AC0AC0AC^{0} " y "la función mod no es calculada por ", donde es la...

La famosa Imagen del mundo de Neil Immerman es la siguiente (haga clic para ampliar):                                         Su clase "Verdaderamente factible" no incluye ninguna otra clase; mi pregunta es entonces: ¿Qué es un problema de AC 0 que se considera poco práctico y por...

Una brecha que siempre supe que realmente no entiendo es entre la complejidad computacional no uniforme y uniforme, donde la complejidad del circuito representa la versión no uniforme y las máquinas de Turing es donde las cosas son uniformes. Supongo que "uniforme" es una forma de restringir la...

El siguiente problema aparece en la lista de Aaronson Diez desafíos grandes para la teoría de la computación cuántica . Es B Q P = B P PB Q N CsiQPAG=siPAGPAGsiQnorteC\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} En otras palabras, ¿se puede comprimir la parte "cuántica" de cualquier algoritmo...

Nosotros sabemos (por ahora unos 40 años, gracias a Adleman, Bennet y Gill) que la inclusión BPP ⊆⊆\subseteq P / poli, y un aún más fuerte BPP / poli ⊆⊆\subseteq P / retención poli. El "/ poly" significa que trabajamos de manera no uniforme (un circuito separado para cada longitud de entrada nnn ),...

¿Cuál es el número mínimo de compuertas binarias necesarias para calcular AND y OR de bits de entrada simultáneamente? El límite superior trivial es 2 n - 2 . Creo que esto es óptimo, pero ¿cómo probarlo? La técnica de eliminación de compuerta estándar no funciona aquí, ya que al asignar una...

En el documento de Pruebas naturales de Razborov-Rudich , página 6, en la parte que discuten que hay "fuertes pruebas de límites inferiores contra modelos de circuito monótono " y cómo encajan en la imagen, están las siguientes oraciones: Aquí el problema no es la constructividad, las...

Supongamos que se nos da un conjunto de n variables booleanas x_1, ..., x_n y un conjunto de funciones m y_1 ... y_m donde cada y_i es el XOR de un subconjunto (dado) de estas variables. El objetivo es calcular el número mínimo de operaciones XOR que necesita realizar para calcular todas estas...

¿Qué sucede si definimos P P A D dePPAD{\bf PPAD} tal manera que, en lugar de un circuito de polimerización de Turing-máquina / polisize, una máquina de Turing de espacio de registro o un circuito A C 0AC0{\bf AC^0} codifique el problema? Recientemente dando algoritmos más rápidos para...

Esta pregunta puede hacerse en el marco de la complejidad del circuito de los circuitos booleanos, o en el marco de la teoría de la complejidad algebraica, o probablemente en muchos otros entornos. Es fácil mostrar, contando argumentos, que existen funciones booleanas en N entradas que requieren...

Antecedentes Una fórmula de lectura única sobre un conjunto de compuertas (también llamada base) es una fórmula en la que cada variable de entrada aparece una vez. Las fórmulas de lectura única se estudian comúnmente sobre la base De Morgan (que tiene las compuertas de 2 bits AND y OR, y la...

Las pruebas naturales son una barrera para probar los límites inferiores de la complejidad del circuito de las funciones booleanas. Ellos no implican directamente cualquier barrera en probar límites inferiores en el la complejidad del circuito. ¿Hay algún progreso hacia la identificación de tales...

El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...