La hipótesis de Riemann de más de ½ siglo de antigüedad tiene profundas implicaciones en las matemáticas y ahora se prueba condicionalmente un gran edificio de teoría matemática y numerosas variantes. Recientemente encontré una referencia a un resultado condicional en TCS basado en la hipótesis de...
Mi pregunta es sobre algoritmos cuánticos para cálculos de QED (electrodinámica cuántica) relacionados con las constantes de estructura fina. Tales cálculos (como se me explicó) equivalen a calcular series similares a Taylor donde α es la constante de estructura fina (alrededor de 1/137) y c k es...
En el artículo de 1965 " Sobre la complejidad computacional de los algoritmos " de Hartmanis y Stearns, los autores conjeturan que si una máquina de Turing en tiempo real calcula el número real en, por ejemplo, la base 10, entonces es un número racional o un número trascendentalrrrrrrr ¿Existe un...
La complejidad de la prueba es un área más básica de la teoría de la complejidad computacional. Un propósito final de esta área es probar , es decir, cualquier comprobador no puede dar una prueba de insatisfacción de la fórmula de entrada dada. nortePAG≠ c o NPAGNP≠coNPNP\neq coNP Un gráfico es...
El problema del isomorfismo gráfico es uno de los problemas más antiguos que resistió la clasificación en problemas o N P- completos. Tenemos evidencias de que no puede ser N P- completo. En primer lugar, el isomorfismo gráfico no puede ser N P- completo a menos que la jerarquía polinómica [1] se...
Siguiendo las preguntas equivalentes sobre NP-Completeness (ver la pregunta de peso y la pregunta dirigida ), me preguntaba cómo los problemas parametrizados se ven afectados por estos atributos. ¿Qué gráficos duros son -Hard en gráficos dirigidos, pero parámetros fijos manejables en gráficos...
Los problemas han sido, en su conjunto, clasificados, gracias a la Complejidad Computacional. Pero, en ecuaciones diferenciales, ¿es posible clasificar las ecuaciones diferenciales en función de su estructura computacional? Por ejemplo, si una ecuación no homogénea de primer orden es...
Dadas dos permutaciones y sobre elementos (es decir, miembros de ), ¿cuál es la complejidad de calcular el orden del subgrupo generado por ? ¡O simplemente de decidir si el subgrupo es de orden(es decir, todo
Es un viejo problema abierto si un teorema de suma directa es válido para la complejidad de comunicación determinista, es decir, si resolver instancias independientes de un problema es t veces más difícil que resolver una sola instancia. [FKNN95] mostró los siguientes resultados:tttttt Un...
Deje ser una constante fija. Dado un número entero , queremos construir una permutación tal que:n σ ∈ S nk > 0k>0 0k>0nortenortenσ∈ Snorteσ∈Snorte\sigma \in S_n La construcción utiliza tiempo y espacio constantes (es decir, el preprocesamiento requiere tiempo y espacio constantes). Podemos...
Me pregunto si puede existir una forma de dar una especie de "forma normal" para los árboles de decisión binarios (BDT) de forma manejable. Más precisamente: una BDT es un árbol con nodos internos etiquetados por variables booleanas y hojas etiquetadas por o . Una BDT representa una función...
Considere el siguiente problema: Dada una matriz , queremos optimizar el número de adiciones en el algoritmo de multiplicación para calcular .v ↦ M vMMMv ↦ Mvv↦Mvv \mapsto Mv Este problema me parece interesante debido a su relación con la complejidad de la multiplicación de matrices (este...
Es bien sabido que ciertas clases de NP -Problemas Tienes dicotomía teoremas, lo que garantiza que todas las tareas en la clase es o NP -Complete o está en P . El mejor resultado conocido es el teorema de dicotomía de Schaefer , junto con una serie de generalizaciones. Entiendo que probar estos...
El siguiente término (usando índices bruijn): BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0))))))))) Cuando se aplica a un número de iglesia se Nevalúa rápidamente a su forma normal en varios evaluadores existentes, incluidos los...
¿Existen ejemplos naturales conocidos de problemas de optimización para los cuales es mucho más fácil producir una solución óptima que evaluar la calidad de una solución candidata dada? En aras de la concreción, podemos considerar problemas de optimización solucionables en tiempo polinómico de la...
Estoy interesado en reducir -Clique a SAT sin hacer que la instancia sea mucho más grande.kkk Clique está en NP, por lo que puede reducirse a SAT utilizando espacio logarítmico. La reducción directa del libro de texto de Garey / Johnson explota la instancia a un tamaño cúbico . Sin embargo,...
Sea un polinomio simétrico , es decir, un polinomio tal que f ( x ) = f ( σ ( x ) ) para todas las x ∈ K n y todas las permutaciones σ ∈ S n . Por conveniencia, podemos suponer que K es un campo finito, para evitar abordar problemas con el modelo de computación.F: Knorte→ KF:Knorte→Kf:\mathbb{K}^n...
La inclusión inversa es obvia, como lo es el hecho de que cualquier lenguaje NP auto reducible en BPP también está en RP. ¿También se sabe que esto es válido para idiomas NP no
Deje que una máquina de Turing probabilística tenga acceso a una moneda injusta que sale cara con probabilidad (los lanzamientos son independientes). Defina B P P p como la clase de lenguajes reconocibles por dicha máquina en tiempo polinomial. Es un ejercicio estándar demostrar que:pagppB...
Deje HALTnHALTnHALT_n denotar la cadena de longitud 2n2n2^n correspondiente a la tabla de verdad del problema de detención para entradas de longitud nnn . Si la secuencia de las complejidades de Kolmogorov K(HALTn)K(HALTn)K(HALT_n) fuera O(1)O(1)O(1) , una de las cadenas de consejos se usaría...