En una respuesta a una pregunta anterior , mencioné la creencia común pero falsa de que la eliminación "gaussiana" se ejecuta en el tiempo O(n3)O(n3)O(n^3) . Si bien es obvio que el algoritmo utiliza operaciones aritméticas O(n3)O(n3)O(n^3) , la implementación descuidada puede crear números con...
Soy un profesional del software y estoy escribiendo una encuesta sobre estructuras algebraicas para la investigación personal y estoy tratando de producir ejemplos de cómo se utilizan estas estructuras en la informática teórica (y en menor grado, otros subcampos de la informática) . Bajo la teoría...
Se conjetura ampliamente que , el exponente óptimo para la multiplicación de matrices, es de hecho igual a 2. Mi pregunta es simple:ωω\omega ¿Qué razones tenemos para creer que ?ω = 2ω=2\omega = 2 Conozco algoritmos rápidos como Coppersmith-Winograd, pero no sé por qué estos podrían...
Mi pregunta es simple: ¿Cuál es el peor tiempo de ejecución del algoritmo más conocido para calcular una descomposición propia de una matriz n × nnorte×norten \times n ? ¿La descomposición propia se reduce a la multiplicación matricial o son los algoritmos más conocidos O ( n3)O(norte3)O(n^3)...
Se cree comúnmente que para todo , es posible multiplicar dos matrices en el tiempo . Alguna discusión está aquí .ϵ > 0ϵ>0\epsilon > 0n × nn×nn \times nO ( n2 + ϵ)O(n2+ϵ)O(n^{2 + \epsilon}) Le pregunté a algunas personas que están más familiarizadas con la investigación si creen que hay un...
Tengo una base muy fuerte en álgebra, a saber álgebra conmutativa, álgebra homológica, teoría de campo, teoría de la categoría, y actualmente estoy aprendiendo geometría algebraica. Soy un experto en matemáticas con una inclinación a cambiar a la informática teórica. Teniendo en cuenta los...
Me gustaría encontrar un algoritmo de tiempo polinómico que determine si el lapso de un conjunto dado de matrices contiene una matriz de permutación. Si alguien sabe si este problema es de una clase de complejidad diferente, sería igual de útil. EDITAR: He etiquetado esta pregunta con la...
Solo conozco dos pruebas del lema de Schwartz-Zippel. La primera prueba (más común) se describe en la entrada de wikipedia . La segunda prueba fue descubierta por Dana Moshkovitz. ¿Hay alguna otra prueba que use ideas sustancialmente diferentes?
Dada una matriz binaria por (las entradas son o ), el problema es determinar si existen dos vectores binarios modo que (todas las operaciones se realizan sobre ). ¿Es este problema NP-hard?mmmnnnMMM000111v1≠v2v1≠v2v_1 \ne v_2Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2ZZ\mathbb{Z} Está claramente en NP, ya que puede...
Hace poco estuve leyendo Las dos dualidades de la computación: tipos negativos y fraccionarios . El documento se expande sobre tipos de suma y tipos de producto, dando semántica a los tipos a - by a/b. A diferencia de la suma y la multiplicación, no hay uno sino dos inversos de exponenciación,...
Sea una matriz entera cuadrada, y sea n un entero positivo. Estoy interesado en la complejidad del siguiente problema de decisión:MMMnnn ¿Es positiva la entrada superior derecha de ?MnMnM^n Tenga en cuenta que el enfoque obvio de la cuadratura iterada (o cualquier otro cálculo explícito) requiere...
Estoy buscando una buena encuesta sobre algoritmos y complejidad del álgebra lineal (operaciones como rango, inverso, valores propios, ... para matrices booleanas, y enteros / racionales) con énfasis en paralelo ( jerarquía ) y algoritmos polytime. No pude encontrar uno reciente....
Descargo de responsabilidad: no soy un teórico de CS. Viniendo del álgebra abstracta, estoy acostumbrado a lidiar con cosas que son iguales a un isomorfismo, pero tengo problemas para traducir este concepto a estructuras de datos. Primero pensé que los morfismos biyectivos teóricos establecidos...
Tengo una educación matemática de pregrado razonable, pero nunca me he sentido 100% cómodo con el álgebra abstracta (las matemáticas de grupos, anillos, campos, etc.). Creo que esto se debió en parte a que necesitaba ver aplicaciones y cualquiera que pudiera encontrar estaba en física, no en CS....
Estoy interesado en la complejidad de resolver ecuaciones lineales módulo k , para k arbitrario (y con un interés especial en las potencias primarias), específicamente: Problema. Para un sistema dado de ecuaciones lineales en incógnitas módulo , ¿existe alguna solución?n kmmmnnnkkk En el...
Estoy buscando un documento de encuesta o un libro que cubra los resultados sobre la complejidad espacial de las operaciones comunes de álgebra lineal, como el rango de la matriz, el cálculo de valores propios, etc. Insisto en la parte de "complejidad espacial" que significa la complejidad del...
¿Alguien puede ayudarme con el siguiente problema? Quiero encontrar algunos valores a i , b jai,bja_i,b_j (mod norteNN ) donde i = 1 , 2 , ... , K , j = 1 , 2 , ... , Ki=1,2,…,K,j=1,2,…,Ki=1,2,…,K, j=1,2,…,K (por ejemplo K = 6K=6K=6 ), dada una lista de valores K 2K2K^2 que corresponden a las...
Una matriz se llama totalmente regular si todas sus submatrices cuadradas tienen rango completo. Tales matrices se usaron para construir superconcentradores. ¿Cuál es la complejidad de decidir si una matriz dada es totalmente regular sobre los racionales? Sobre campos finitos? Más en general,...
Rn\mathbb{R}^n⟨⋅,⋅⟩\langle \cdot, \cdot \ranglemmv1,v2,…,vmv_1, v_2, \ldots, v_mx∈Rnx \in \mathbb{R}^nmin i ⟨ x , v i ⟩ mini⟨x,vi⟩\min_i \langle x, v_i \rangleO ( n m )O(nm)O(nm) n = 2 n=2n = 2O ( conecto 2 m )O(log2m)O(\log^2 m) Lo único que se me ocurre es lo siguiente. Es una consecuencia...
Una propiedad básica de los espacios vectoriales es que un espacio vectorial de dimensión n - d puede caracterizarse por d restricciones lineales linealmente independientes, es decir, existen d vectores linealmente independientes w 1 , ... , w d ∈ F n 2 que son ortogonales a V .V⊆Fn2V⊆F2nV...