Creo que no lo entiendo, pero la conversión me parece una conversión que no hace nada, un caso especial de conversión donde el resultado es solo el término en la abstracción lambda porque no hay nada hacer, una especie de conversión sentido.β β βηη\etaββ\betaββ\betaββ\beta Entonces, tal vez...
Hay una multitud de algoritmos que pueden analizar una gramática libre de contexto en tiempo . Usando la multiplicación de matrices, incluso se puede ir asintóticamente más rápido que eso.O ( n3)O(n3)O(n^3) Sin embargo, todos los algoritmos para analizar CFG arbitrarios que conozco tienen un uso...
La operación de votación mayoritaria aparece con bastante frecuencia en la tolerancia a fallas (y sin duda en otros lugares), donde la función genera un bit igual al valor que aparece con mayor frecuencia en el valor de los bits de entrada. Para simplificar, supongamos que cada vez que la entrada...
XORification es la técnica para hacer que una función o fórmula booleana sea más difícil al reemplazar cada variable por el XOR de k ≥ 2 variables distintas x 1 ⊕ ... ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Soy consciente de los usos de esta técnica en la complejidad de...
¿La prueba automática de teoremas y la búsqueda de pruebas son más fáciles en lógicas subestructurales lineales y otras proposicionales que carecen de contracción? ¿Dónde puedo leer más sobre la demostración automática de teoremas en estas lógicas y el papel de la contracción en la búsqueda de...
¿Hay algún algoritmo para la resolución SAT que no esté basado en DPLL? ¿O todos los algoritmos utilizados por los solucionadores SAT están basados en
Es bien sabido que las computadoras cuánticas son estrictamente más poderosas que sus contrapartes clásicas en términos de complejidad de consulta . ¿Existen otros modelos (naturales o artificiales) que estén estrictamente entre lo cuántico y lo clásico en términos de complejidad de consulta?...
Veo mucha investigación sobre la hipercomputación en la década de 1990, pero en los últimos años parece haber poco trabajo sobre el tema. ¿Es cierto que la investigación en esta área ha disminuido? Si es así, ¿cuáles podrían ser los motivos? ¿Se demostró convincentemente que esta área no era...
¿Qué se sabe sobre la complejidad exacta del problema de supercuerdas más corto? ¿Se puede resolver más rápido que O∗(2n)O∗(2n)O^*(2^n) ? ¿Existen algoritmos conocidos que resuelvan la supercadena más corta sin reducir a TSP? UPD: suprime los factores polinomiales.O∗(⋅)O∗(⋅)O^*(\cdot) El...
Creo que sería una buena idea hacer una lista de teoremas que indiquen que P no es igual a NP si y solo si tales y tales salidas, alguna clase de complejidad está contenida en otra clase de complejidad y así sucesivamente.
Sea una fórmula CNF satisfactoria con n variables y m cláusulas. Sea S F 1 el espacio de solución de F 1 .F1F1F_1nortennmetrommSF1SF1S_{F_1}F1F1F_1 Considere el problema de determinar, dado , otra Fórmula CNF F 2 con el mismo conjunto de variables que F 1 , con S F 2 = S F 1 (el mismo espacio de...
IP = PSPACE aparece como el ejemplo canónico de un resultado no relativizante, y la prueba de esto es que existe un oráculo tal que , mientras que {\ sf CONP} ^ O \ subseteq {\ sf PSPACE} ^ O para todos los oráculos O .c o N P O ⊈ I P O c o N P O ⊆ P S P A C E O OOOOc o N PO⊈ I...
Estoy trabajando en un conjunto de problemas para una clase, y pensé en una pregunta relacionada con lo que estaba trabajando. ¿Existe un número mínimo de estados que debe tener un autómata finito para aceptar cadenas binarias que representan números divisibles por un entero n? En un conjunto de...
He buscado por todas partes tales aplicaciones y la mayoría de las veces me he quedado corto. Puedo encontrar muchas aplicaciones de topología y estructuras similares en conjuntos contables (o incontables), pero rara vez encuentro conjuntos incontables como objeto de estudio por parte de...
¿Cuáles son los algoritmos eficientes conocidos para calcular un determinante de una matriz entera con coeficientes en , el anillo de residuos módulo . El número puede no ser primo sino compuesto (por lo que los cálculos se realizan en anillo, no en un campo).
¿Se ha trabajado en cómo la complejidad de las instancias aleatorias de # 2-SAT varía con la densidad de la cláusula? Es decir: ¿cómo varía la dificultad de contar soluciones satisfactorias para una instancia de 2-SAT generada aleatoriamente , a medida que varía la densidad de la cláusula? En...
Supongamos que es un árbol de grado constante cuya estructura no conocemos. El problema es generar el árbol haciendo preguntas de la forma: "¿El nodo encuentra en la ruta del nodo al nodo ?". Suponga que cada consulta puede ser respondida en tiempo constante por un oráculo. Conocemos el valor de ,...
Como saben, hay muchas anomolias para las máquinas de Turing de cinta única cuando el tiempo es : simulación de TM de cinta múltiple, simulación de alfabeto de cinta más grande con solo , capacidad de construcción de tiempo, teorema de la falta de rigidez del tiempo,
El complejo zoológico no tiene mucho sobre . Estoy buscando un buen problema que se encuentra en los niveles superiores de la jerarquía, es decir, un problema en pero no se sabe que está en .SCSC\mathsf{SC} † D T i m e S p a c e ( n O ( 1 ) , lg O ( 1 ) n) D T i m e S p a c e ( n O ( 1 ) , lg 2...
Soy un físico de corazón, por lo que creo que la computación cuántica unidireccional es brillante. En particular, la computación cuántica basada en la medición del estado gráfico (MBQC) ha sido un desarrollo realmente agradable en la investigación de la computación cuántica, originada por...