Estoy escribiendo mi tesis de maestría en CS y estoy trabajando con el análisis de alias. Lo que me interesa es el análisis intraprocesal, sensible al flujo de alias y may-may para lenguajes similares a Java. Estoy buscando textos que describan los conceptos básicos de este tema de manera...
Escuché de un resultado en el color aproximado del gráfico, pero no puedo encontrar la fuente. El resultado es: Para cada constante existe una suficientemente grande como para que colorear un gráfico coloreable con colores sea NP-duro.hhhkkkkkkh khkhk ¿Podría alguien señalarme el documento...
Dado un gráfico dirigido, queremos decidir si contiene un ciclo dirigido de longitud par. Este artículo de 1997 de YUSTER y ZWICK afirma que no se sabe que el problema esté en ni que se sepa que es completo.PAGPAGPnortePAGnortePAGNP ¿Hay algún resultado reciente que resuelva la complejidad del...
En el Capítulo 13 "Objetos atómicos" del libro "Algoritmos distribuidos" de Nancy Lynch, se demuestra que la linealización (también conocida como atomicidad) es una propiedad de seguridad. Es decir, su propiedad de rastreo correspondiente es no vacía, con prefijo cerrado y límite cerrado , como se...
¿Cuál es la definición estándar de Planar 3-SAT? He visto varias definiciones diferentes. ¿Cuál fue el documento original que lo definió y demostró que era NP
¿Hay algún problema que se pueda resolver en el tiempo polinomial solo si P! = NP, y de otra manera se puede resolver en (digamos) tiempo?O(2n)O(2n)O(2^n) Un ejemplo simple sería: Si P! = NP, calcule una prueba de primalidad para un número aleatorio de n bits, de lo contrario, evalúe una posición...
nnortenx1,…,xnx1,…,xnx_1,\ldots, x_nkkkn>kn>kn > kmaxi≠jVar(xTixj)maxi≠jVar(xiTxj)\max_{i\neq j} \mathrm{Var}(x_i^T x_j)E[xTixj]=0E[xiTxj]=0\mathbb{E}[x_i^Tx_j]=0 Intenté algunas distribuciones y casi todas tienen varianza 1/k1/k1/k . Por ejemplo, tanto la distribución en la que cada...
Antecedentes: el procesamiento de transacciones ha sido un tema de investigación tradicional en la teoría de bases de datos. Hoy en día, las transacciones distribuidas se popularizan por los sistemas de almacenamiento distribuido a gran escala que generalmente implican la partición de datos...
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...
Es un hecho bastante conocido que derivar una contradicción de una desigualdad (por ejemplo, ) en la teoría de tipo Martin-Loef requiere un universo.( 0 = 1 ) → ⊥(0=1)→⊥(0=1) \to \bot La prueba también es bastante sencilla: en ausencia de universos, podemos borrar las dependencias de cualquier...
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...
Los transductores considerados aquí son aquellos que Wikipedia llama transductores de estado finito . El comportamiento de un transductor , es decir, la relación que calcula, se escribe : una palabra es una salida para iff .TTT[T][T][T]yyyxxxx[T]yx[T]yx[T]y Pregunta: ¿Se puede resolver el...
¿Dónde puedo encontrar una introducción a los autómatas probabilísticos y lo que reconocen (ciertas funciones desde palabras hasta )? ¿Existe un término estándar para tales funciones que son reconocidas por los autómatas probabilísticos, análoga a "lenguajes regulares" para lo que reconocen los...
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...
Supongamos que es un lenguaje parametrizado con respecto a algún alfabeto . La división de es , el conjunto de instancias en que tienen el parámetro . La clase de complejidad contiene los lenguajes parametrizados modo que para cada , posiblemente con un algoritmo diferente y un tiempo de ejecución...
Motivación : Mientras desarrollamos herramientas para el control de versiones de datos, terminamos buscando algoritmos para "diferenciar" dos conjuntos de enteros, creando una secuencia de transformaciones que llevan un conjunto de enteros al otro. Pudimos reducir ese problema al siguiente problema...
El término inversión de programa tiene múltiples matices de significado, pero probablemente comenzó con el trabajo de J. McCarthy de 1956 La inversión de las funciones definidas por las máquinas de Turing en el contexto de la IA. Hasta ahora se han descubierto muchas conexiones entre la inversión...
Estoy en una situación en la que necesito demostrar que la verificación de tipos es decidible para un cálculo de tipo dependiente en el que estoy trabajando. Hasta ahora, he podido demostrar que el sistema se está normalizando fuertemente y, por lo tanto, que la igualdad de definición es...
Me pregunto si alguien puede darme la intuición detrás de por qué la estricta positividad de los tipos de datos inductivos garantiza una fuerte normalización. Para ser claros, veo cómo tener ocurrencias negativas conduce a la divergencia, es decir, al definir: data X where Intro : (X->X) ->...