En general, decidir si una ecuación de diofantina tiene alguna solución entera es equivalente al problema de detención. Creo que decidir si una ecuación de diofantina cuadrática tiene alguna solución es NP-completo. ¿Existe una restricción adicional en las ecuaciones involucradas que produce un...
En cs.stackexchange , pregunté sobre la biblioteca algebird scala en github, especulando sobre por qué podrían necesitar un paquete de álgebra abstracta. La página de github tiene algunas pistas: Implementaciones de monoides para algoritmos de aproximación interesantes, como el filtro Bloom,...
EDITAR (por Tara B): Todavía estaría interesado en una referencia a una prueba de esto, ya que tuve que demostrarlo yo mismo para mi propio artículo. Estoy buscando la prueba del Teorema 4 que aparece en este documento: Una jerarquía infinita de intersecciones de lenguajes sin contexto por Liu y...
Sabemos que el registro del rango de una matriz 0-1 es el límite inferior de la complejidad de comunicación determinista, y el registro del rango aproximado es el límite inferior de la complejidad de la comunicación aleatoria. La brecha más grande entre la complejidad de comunicación determinista y...
Durante mi trabajo se me ocurrió el siguiente problema: Estoy tratando de encontrar una matriz ( 0 , 1 ) M , para cualquier n > 3 , con las siguientes propiedades:n×nn×nn \times n (0,1)(0,1)(0,1)MMMn>3n>3n > 3 El determinante de es par.MMM Para cualquier subconjunto no vacío con | Yo |...
Digamos que tenemos un poliedro en forma estándar: A x = bx ≥ 0UNAX=siX≥0 0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} ¿Hay algún método conocido para encontrar un hiperplano que divide el poliedro de manera que el número...
¿Hay alguna construcción conocida de un código de corrección de error lineal (con parámetros razonables), de modo que cuando se le da un vector booleano , también devuelve un vector booleano whp? (aunque se acabó ) v ∈ { 0 , 1 } n F qE C C : Fnorteq→ FmetroqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n...
En el artículo seminal de Bernstein y Vazirani, "Teoría de la complejidad cuántica", muestran que una transformación unitaria dimensional puede ser aproximada eficientemente por un producto de lo que llaman "rotaciones casi triviales" y "cambios de fase casi triviales".rered Las "rotaciones casi...
Sé que Gaussian Elimination toma operaciones aritméticas , pero no estoy seguro de si se conocen algoritmos mejores.O (
En la complejidad de la comunicación, la conjetura de log-rank establece que cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Donde cc(M)cc(M)cc(M) es la complejidad de comunicación de M(x,y)M(x,y)M(x,y) y rk(M)rk(M)rk(M) es el rango de MMM (como una matriz) sobre los...
Esta es una versión especializada de una pregunta anterior: Complejidad de encontrar la descomposición propia de una matriz . Para las matrices simétricas NxN, se sabe que el tiempo O (N ^ 3) es suficiente para calcular la descomposición propia. La pregunta es: ¿podemos lograr una complejidad...
Según el título, aparte de usar un solucionador de LP de propósito general, ¿hay un enfoque para resolver sistemas de desigualdades sobre las variables Xyo, ... , xkXyo,...,Xkx_i, \ldots, x_k donde las desigualdades tienen la forma ∑yo ∈ yoXyo< ∑j ∈ JXj∑yo∈yoXyo<∑j∈JXj\sum_{i \in I} x_i <...
Hay un programa lineal para el que quiero no solo una solución, sino una solución que sea lo más central posible en el politopo que asuma el valor mínimo. A priori, esperamos que la cara de minimización sea de alta dimensión por varias razones, incluyendo que la función objetivo que se minimiza es...
Considere un espacio de Hilbert . Una base de producto no extensible (UPB) es un conjunto de vectores de producto | v i ⟩ = | v 1 i ⟩ ⊗ ⋯ ⊗ | v n i ⟩ tal que:H= H1⊗ ⋯ ⊗ HnorteH=H1⊗⋯⊗HnorteH = H_1 \otimes \dots \otimes H_nEl | vyo⟩ = | v1yo⟩ ⊗ ⋯ ⊗ | vnorteyo⟩El |vyo⟩=El |vyo1⟩⊗⋯⊗El |vyonorte⟩\vert...
Estoy usando un cálculo de la matriz de varianza-covarianza en un programa que escribí (para el análisis de componentes principales), y me pregunto cuál es su complejidad. Aunque obviamente la descomposición del vector propio está causando el mayor impacto en el rendimiento, me pregunto cuánto de...
En comparación con los espectros de gráficos no dirigidos, que corresponden a matrices simétricas, los espectros de gráficos dirigidos no son muy conocidos: Se sabe que un gráfico dirigido G=(V,E)G=(V,E)G = (V,E) tiene una matriz de adyacencia A(G)A(G)A(G) cuyos valores propios son binarios...
Estoy buscando trabajo para calcular el cierre transitivo de una relación afín en el siguiente sentido: Sea la relación definida por un sistema de desigualdades lineales sobre las variables reales , es decirx 1 , ... , x n , x ′ 1 , ... , x ′
Considere los siguientes problemas: Problema de vectores ortogonales Entrada: Un conjunto SSS de nnn vectores booleanos de longitud ddd . Pregunta: ¿Existen vectores distintos v 1v1v_1 y v 2 ∈ S dev2∈Sv_2 \in S modo que v 1 ⋅ v 2 = 0v1⋅v2=0v_1 \cdot v_2 = 0 ? Problema de vectores no...