Robin Milner definió bigraphs como un tipo de estructura gráfica con una estructura similar a un gráfico, pero donde los nodos se pueden anidar. Generalizan cálculos de procesos como CCS y el cálculo , pero Milner parece haber tenido la intención de que se usen de manera mucho más general: las...
Estoy buscando información sobre la complejidad computacional de la multiplicación de matrices de matrices rectangulares. Wikipedia afirma que la complejidad de multiplicar por B ∈ R n × p es O ( m n p ) (multiplicación del libro escolar).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in...
Let ser un lenguaje, entonces definimos la congruencia sintáctica como u ~ v : ⇔ ∀ x , y ∈ X * : x T y ∈ L ↔ x v y ∈ L y el cociente monoid X * / ~ L es llamado el monoide sintáctica de L .L⊆X∗L⊆X∗L \subseteq X^{\ast}u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈Lu∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u \sim v :\Leftrightarrow...
Considere un vector de variables x⃗ x→\vec{x} , y un conjunto de restricciones lineales especificadas por Ax⃗ ≤bAx→≤bA\vec{x}\leq b . Además, considere dos
Pregunta. En su artículo, Simulación mejorada de circuitos estabilizadores , Aaronson y Gottesman afirman que simular un circuito CNOT es ⊕L -completo (bajo reducciones de espacio de registro). Está claro que está contenido en ⊕L ; ¿Cómo se mantiene el resultado de la dureza? Equivalente: ¿hay...
¿Existe , un lenguaje completo NP o P que tiene una familia de grupos de simetría (o grupoide , pero luego las preguntas algorítmicas se vuelven más abiertas) actuando (en tiempo polinómico) en conjuntos tal que hay pocas órbitas, es decir, tal que para suficientemente grande...
ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Cuando escribo polinomios aleatorios con grados yn variables, puedes pensar en cada...
Mi experiencia es en teoría / lógica de complejidad (donde solo hay un proceso la mayor parte del tiempo), y en computación distribuida (donde hay procesos y uno o más pueden fallar con el tiempo). Sin embargo, ahora quiero poder decir algo sobre un proceso que genera / crea / deriva de otro...
Estaba buscando la multiplicación de matrices, así que primero visito los algoritmos de multiplicación de matrices wiki . En las referencias encontré un artículo que afirma que usa el algoritmo , leería el artículo pero es complicado y lo haré toma demasiado tiempo leerlo, pero si hay alguien que...
Tengo un problema algebraico relacionado con vectores en el campo GF (2). Supongamos que sean (0,1) -vectores de dimensión n , ym = n O ( 1 ) . Encuentre un algoritmo de tiempo polinómico que encuentre un vector (0,1) u de la misma dimensión tal que u no sea la suma de ningún vector ( log n ) O ( 1...
Sea un cuadrado n × nnorte×norten\times n matriz real UNUN{\bf A} y dos vectores XX{\bf x} y sisi{\bf b} de longitud nortenorten , de modo que A x = b .UNX=si.{\bf A}{\bf x}={\bf b}. Resolver XX{\bf x} través de la eliminación gaussiana estándar produce una complejidad agregada de casi O (...
¿Qué se sabe sobre la clase de idiomas reconocidos por autómatas finitos que tienen el mismo estado inicial y de aceptación? Este es un subconjunto adecuado de los idiomas regulares (ya que cada idioma contiene la cadena vacía), pero ¿qué tan débil es? ¿Existe una caracterización algebraica...
Dada una matriz A con entradas racionales. ¿Cuál es la complejidad para verificar que A es diagonalizable?n × nnorte×norten\times nUNUNAUNUNA Sospecho que esto se puede hacer en P, pero no conozco ninguna referencia. Sin embargo, una pregunta más interesante es, ¿hay alguna clase de complejidad...
¿Qué tan difícil es encontrar la solución más escasa para un sistema de ecuaciones lineales? Más formalmente, considere el siguiente problema de decisión: Instancia: Un sistema de ecuaciones lineales con coeficientes enteros y un número CCc . Pregunta: ¿Existe una solución para el sistema con al...
Estoy buscando una lista sobre la complejidad conocida o desconocida de varios problemas teóricos / algebraicos de números. Por ejemplo, El MCD en está abierto,NC1NC1NC^1 factoring en está abierto,PPP la cohomología informática de la gavilla es -duro#P#P\#P , Arora y Barak afirman que una...
Sabemos, por ejemplo, por Koutis-Miller-Peng (basado en el trabajo de Spielman y Teng), que podemos resolver muy rápidamente los sistemas lineales Ax=bAx=bA x = b para las matrices AAA que son la matriz de Laplacia de gráficos para algunos gráficos dispersos con pesos de borde no negativos . Ahora...
Supongamos que queremos multiplicar matrices. El algoritmo de multiplicación de matriz lenta se ejecuta en el tiempo O ( n 3 ) y usa memoria O ( n 2 ) . La multiplicación matricial más rápida se ejecuta en el tiempo n ω + o ( 1 ) , donde ω es la constante de álgebra lineal, pero ¿qué se sabe sobre...
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,...
Deje una matriz real ( ) {\ bf A} con la propiedad de que cualquier colección de k columnas es de rango completo.k ≤ nk×nk×nk\times nk≤nk≤nk\le nAA{\bf A}kkk P: ¿Hay una manera eficiente de encontrar determinísticamente un vector aa{\bf a} modo que la matriz aumentada A′=[Aa]A′=[Aa]{\bf A}' =...
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...