preguntas sobre límites inferiores en funciones, generalmente la complejidad de un algoritmo o un problema
La informática teórica ha proporcionado algunos ejemplos del "precio de la abstracción". Los dos más destacados son para la eliminación y clasificación gaussianas. A saber: Se sabe que la eliminación gaussiana es óptima para, por ejemplo, calcular el determinante si restringe las operaciones a...
Al diseñar un algoritmo para un nuevo problema, si no puedo encontrar un algoritmo de tiempo polinómico después de un tiempo, podría intentar probar que es NP-hard en su lugar. Si tengo éxito, he explicado por qué no pude encontrar el algoritmo de tiempo polinómico. No es que sepa con certeza que...
¿Cuáles son los mejores límites inferiores actuales para el tiempo y la profundidad del circuito para
En la década de 1980, Razborov demostró que hay funciones booleanas monótonas explícitas (como la función CLIQUE) que requieren exponencialmente muchas puertas AND y OR para computar. Sin embargo, la base {AND, OR} sobre el dominio booleano {0,1} es solo un ejemplo de un conjunto de puertas...
Deje que PRIMES (también conocido como prueba de primalidad ) sea el problema: Dado un número natural nnn , ¿es nnn un número primo? Deje que FACTORING sea el problema: Dados los números naturales , m con 1 ≤ m ≤ n , ¿ n tiene un factor d con 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1 \leq m \leq...
La codicia, por falta de una palabra mejor, es buena. Uno de los primeros paradigmas algorítmicos enseñados en el curso introductorio de algoritmos es el enfoque codicioso . El enfoque codicioso da como resultado algoritmos simples e intuitivos para muchos problemas en P. Más interesante, para...
Hace unos años, Joel Friedman realizó algunos trabajos relacionados con los límites del circuito inferior a la cohomología de Grothendieck (ver documentos: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ) ¿Esta línea de pensamiento ha aportado nuevas ideas sobre la complejidad...
El reciente resultado innovador del límite inferior de la complejidad del circuito de Ryan Williams proporciona una técnica de prueba que utiliza el resultado del límite superior para demostrar la complejidad de los límites inferiores. Suresh Venkat en su respuesta a esta pregunta, ¿hay resultados...
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...
Pregunta: ¿Cuál es el límite inferior de tamaño de fórmula más conocido para una función explícita en AC 0 ? ¿Existe una función explícita con un límite inferior ?Ω ( n2)Ω(n2)\Omega(n^2) Fondo: Como la mayoría de los límites inferiores, los límites inferiores del tamaño de la fórmula son...
Necesito calcular la mediana de carrera: Entrada: nnn , kkk , vector .(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Salida: vector , donde es la mediana de .(y1,y2,…,yn−k+1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1})yiyiy_i( xyo, xi + 1, ... , xi + k - 1)(Xyo,Xyo+1,...,Xyo+k-1)(x_i, x_{i+1},...
Está claro que cualquier problema que sea decidible en el espacio de registro determinista ( ) se ejecuta en la mayoría de los casos de polinomios ( ). Hay una gran cantidad de clases de complejidad entre y . Los ejemplos incluyen , , , , , . Se cree ampliamente que .P L P N L L o g C F L N C i S A...
Un polinomio es una proyección monótona de un polinomio si = poly , y hay una asignación manera que . Es decir, es posible reemplazar cada variable de por una variable o una constante o para que el polinomio resultante coincida con . F( x1, ... , xnorte)f(x1,…,xn)f(x_1,\ldots,x_n)m ( n ) π : { y 1...
Sé que trivialmente la función OR en nortenn variables X1, ... , xnortex1,…,xnx_1,\ldots, x_n puede representarse exactamente por el polinomio p ( x1, ... , xnorte)p(x1,…,xn)p(x_1,\ldots,x_n) como tal: p ( x1, ... , xnorte) = 1 - ∏nortei = 1( 1 - xyo)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) =...
Además de la complejidad de comunicación (determinista) de una relación , otra medida básica para la cantidad de comunicación necesaria es el número de partición de protocolo . La relación entre estas dos medidas se conoce hasta un factor constante. La monografía de Kushilevitz y Nisan (1997) daRc...
Siguiendo con una pregunta anterior , ¿Cuáles son los mejores límites inferiores del espacio actual para SAT? Con un límite inferior de espacio, me refiero al número de celdas de cintas de trabajo utilizadas por una máquina de Turing que utiliza un alfabeto binario de cintas de trabajo. Un...
A la luz del reciente abismo en el resultado de profundidad-3 (que entre otras cosas produce un circuito aritmético de profundidad -3 para el determinante sobre ), Tengo las siguientes preguntas: Grigoriev y Karpinski demostraron un límite inferior para cualquier circuito aritmético de...
La redacción exacta del título se debe a Anand Kulkarni (quien propuso que se creara este sitio). Esta pregunta se hizo como una pregunta de ejemplo, pero tengo una curiosidad increíble. Sé muy poco acerca de la geometría algebraica y, de hecho, solo tengo una comprensión superficial y de pregrado...
Preámbulo Goldwasser, Micali y Rackoff y Babai introdujeron sistemas de prueba interactivos y protocolos Arthur-Merlin en 1985. Al principio, se pensó que el primero es más poderoso que el segundo, pero Goldwasser y Sipser demostraron que tienen el mismo poder ( con respecto al reconocimiento del...
Usando el algoritmo carry look ahead podemos calcular la suma usando una familia de circuitos tamaño de polinomio de profundidad 5 (o 4?) . ¿Es posible reducir la profundidad? ¿Podemos calcular la suma de dos números binarios usando una familia de circuitos de tamaño polinómico con una profundidad...