A veces se afirma que la Teoría de la Complejidad Geométrica de Ketan Mulmuley es el único programa plausible para resolver las preguntas abiertas de la teoría de la complejidad como la pregunta P vs. NP. Ha habido varios comentarios positivos de famosos teóricos de la complejidad sobre el...
Según tengo entendido, el programa de teoría de la complejidad geométrica intenta separar al demostrar que el funcionamiento de una matriz de valores complejos es mucho más difícil de calcular que el determinante.VP≠VNPVP≠VNPVP \neq VNP La pregunta que tuve después de hojear los documentos de GCT:...
En general, sabemos que la complejidad de probar si una función toma un valor particular en una entrada dada es más fácil que evaluar la función en esa entrada. Por ejemplo: Evaluar el permanente de una matriz entera no negativa es # P-hard, pero determinar si dicho permanente es cero o no está...
Sea un entero positivo fijo de tamaño bits.nAAAnnn Se permite preprocesar este número entero según corresponda. Dado otro entero positivo de tamaño bits, ¿cuál es la complejidad de la multiplicación ?m A BBBBmmmABABAB Tenga en cuenta que ya tenemos algoritmos . La pregunta aquí es si podemos...
Recientemente he visto varios artículos sobre arxiv que se refieren a un sistema de prueba llamado suma de cuadrados. ¿Alguien puede explicar qué es una prueba de suma de cuadrados y por qué esas pruebas son importantes / interesantes? ¿Cómo se relacionan con otros sistemas de prueba algebraica?...
La teoría de categorías y el álgebra abstracta tratan la forma en que las funciones se pueden combinar con otras funciones. La teoría de la complejidad trata de cuán difícil es calcular una función. Es extraño para mí que no haya visto a nadie combinar estos campos de estudio, ya que parecen pares...
Al leer un documento sobre el uso de métodos algebraicos para detectar algunos subgrafos inducidos, parece que el ideal de borde es una herramienta importante que conecta el álgebra conmutativa y la teoría de grafos. Como no estoy familiarizado con los cálculos de objetos algebraicos, ¿hay alguna...
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...
Muchos criptosistemas de clave pública tienen algún tipo de seguridad demostrable. Por ejemplo, el criptosistema Rabin es probablemente tan difícil como factorizar. Me pregunto si existe ese tipo de seguridad comprobable para los criptosistemas de clave secreta, como AES. Si no es así, ¿cuál es la...
Quiero aprender sobre algoritmos algebraicos y complejidad thoery. En particular, estoy interesado en PIT. ¿Existe un conjunto de apuntes, libros, documentos y encuestas para estudiantes que han leído libros de texto estándar sobre teoría como el libro de Sipser o el libro de texto de complejidad...
BPPBPP\mathbf{BPP}PP\mathbf{P}polypoly\mathrm{poly} ( min , + )(max,+)(max,+)(\max,+)(min,+)(min,+)(\min,+) Deje ser un semired. Un patrón cero de una secuencia de polinomios en es un subconjunto para el que existen y tal que para todo , si y sólo si . Es decir, las gráficas de exactamente esos...
La fórmula más pequeña conocida para el determinante tiene un tamaño acuerdo con el folclore (o Ran Raz en su papel Las fórmulas multilineales para permanente y determinante son de tamaño superpolinomial ).norteO (logn )norteO(Iniciar sesiónnorte)n^{\mathcal O(\log n)} ¿Tienes alguna referencia...
La eliminación gaussiana hace que el determinante de una matriz de tiempo polinómico sea computable. La reducción de la complejidad en la computación del determinante, que de otro modo es la suma de términos exponenciales, se debe a la presencia de signos negativos alternativos (la falta de lo que...
En su artículo seminal Algoritmos teóricos grupales para multiplicaciones matriciales , Cohn, Kleinberg, Szegedy y Umans presentan el concepto de rompecabezas único y solucionable (definido a continuación) y la capacidad de USP. Afirman que Coppersmith y Winograd, en su innovador papel Matrix...
Un problema importante en TCS es el problema de expresar un permanente como determinante. Estaba leyendo el artículo de Agrawal Determinante versus Permanente y en un párrafo afirma que el problema inverso es fácil. Es fácil ver que el determinante de una matriz se puede expresar como la...
En el famoso contraejemplo para el isomorfismo gráfico mediante el método Weisfeiler-Lehman (WL) , Cai, Furer e Immerman construyeron el siguiente dispositivo en este documento . Construyen un gráfico dado porXk=(Vk,Ek)Xk=(Vk,Ek)X_k = (V_k,
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...
Deje ser un campo. Como de costumbre, para una definimos como la complejidad lineal de sobre . Sea el conjunto de monomios de , es decir, los monomios que aparecen en con coeficiente distinto de cero.kkkf∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in k[x_{1},x_{2},\ldots,x_{n}]L(f)L(f)L(f)fffkkkFFFffffff...
Estoy tratando de entender la relación entre la complejidad algorítmica y la complejidad del circuito de los determinantes y la multiplicación de matrices. Se sabe que el determinante de una matriz se puede calcular en el tiempo , donde es el tiempo mínimo requerido para multiplicar dos matrices....
La matriz de Moore es similar a la matriz de Vandermonde pero tiene una definición ligeramente modificada. http://en.wikipedia.org/wiki/Moore_matrix ¿Cuál es la complejidad de calcular el determinante de un rango completo de la matriz de Moore módulo algún entero?n×nn×nn \times n ¿Se puede...