El análisis suavizado se ha aplicado muchas veces para comprender el tiempo de ejecución de algoritmos exactos para muchos problemas como la programación lineal y k-means. Hay resultados bastante generales en este ámbito, por ejemplo, Heiko Röglin y Berthold Vöcking, Análisis suavizado de la...
¿Cuál es la relación entre y ? En otras palabras, ¿son aproximables los problemas que admiten una búsqueda local de tiempo polinómico? ¿Los problemas de optimización aproximada implican un algoritmo de búsqueda local en
Actualmente estoy haciendo una investigación de lenguaje formal que involucra clases de idiomas por encima de Regular pero debajo de Context Free. Estoy viendo cosas como máquinas multicontadores limitados por inversión, máquinas de contador de una sola pila, CFL deterministas, etc. Me pregunto si...
Dado un juego determinista de suma cero de información parcial con solo un número finito de estados, cuyos posibles resultados son [perder, empatar, ganar] con valores [-1,0, + 1] respectivamente, ¿cuál es la complejidad de aproximar el valor de tales un juego aditivamente dentro de...
TC0TC0\mathsf{TC^0} dTC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd La entrada del zoológico para TC0TC0\mathsf{TC^0} solo menciona la separación entre la profundidad 2 y 3. ¿También hay una referencia estándar para el hecho de que la jerarquía AC0dACd0\mathsf{AC^0_d} no...
Esta es una pregunta interesante que he encontrado en la web. Dada una matriz que contiene n números (sin información sobre ellos), debemos preprocesar la matriz en tiempo lineal para que podamos devolver los k elementos más pequeños en el tiempo O (k), cuando se nos da un número 1 <= k <=...
¿Podemos probar un resultado de concentración aguda en la suma de variables aleatorias exponenciales independientes, es decir, Sea X1,…XrX1,…XrX_1, \ldots X_r sean variables aleatorias independientes tales como Pr(Xi<x)=1−e−x/λiPr(Xi<x)=1−e−x/λiPr(X_i < x) = 1 - e^{-x/\lambda_i} . Deje...
Esta pregunta está motivada por esta publicación, ¿Puedes identificar la suma de dos permutaciones en el tiempo polinómico? , y mi interés en las propiedades computacionales de las permutaciones. Una secuencia de diferencias de una permutación π de los números 1 , 2 , ... n + 1 se forma al...
Tengo un autómata finito no determinista realmente grande y necesito convertirlo al DFA. Por grande me refiero a más de 40 000 estados. Hasta ahora he realizado algunos experimentos y programado el algoritmo predeterminado que busca en la tabla (como se describe aquí ), pero incluso después de la...
¿Cuáles son algunas aplicaciones concretas y convincentes para estimar el volumen de poliedros convexos del tipo considerado en los documentos más recientes sobre métodos de caminata aleatoria? Estos documentos sobre estimación de volumen mencionan la integración numérica como una motivación....
Este documento demuestra que en un juego con puertas y placas de presión, es difícil para PSPACE determinar si el avatar (del jugador) puede o no alcanzar una ubicación determinada. Esto se demuestra mediante una reducción de TQBF , y la longitud de las soluciones resultantes depende...
¿Existe una cola de prioridad entera que usa palabras de espacio con las siguientes operaciones, todo en el peor de los casos y sin acceso a aleatoriedad:O(n)O(n)O(n) createEmptyQueueen para alguna constante c .O(lgcU)O(lgcU)O(lg^c U)ccc inserten .O(1)O(1)O(1) deleteMinen , donde δ min es la...
Los autómatas de estado finito residual (RFSA, definidos en [DLT02]) son NFA que tienen algunas características agradables en común con los DFA. En particular, siempre hay un RFSA canónico de tamaño mínimo para cada idioma regular, y el idioma reconocido por cada estado en el RFSA es residual, al...
Contenidos entre cada nivel de la jerarquía polinómica hay varias clases de complejidad, que incluyen , DP , BH k y Σ P i ∩ Π P i . Por falta de una mejor terminología, me referiré a estas y a otras como clases intermedias entre los niveles i e i + 1 en la jerarquía polinómica. Para los propósitos...
Recientemente comencé a leer mucho sobre la complejidad de las pruebas y realmente he disfrutado lo que he estado leyendo. Realmente me gustaría aprender más sobre esto, pero estoy teniendo dificultades para encontrar un buen material para principiantes para comenzar. ¿Alguien podría recomendar...
Muy similar a mi pregunta publicada anteriormente . Esta vez, sin embargo, el gráfico no está dirigido. Dado Un gráfico G no dirigido sin múltiples bordes o bucles,GGG Un vértice fuente sss , Un vértice objetivo ttt , Longitud máxima del camino lll , Busco - A subgrafo de G que contiene...
Estoy tratando de entender a qué clase de complejidad pertenece el siguiente problema: Problema de raíz polinómica exponencial (EPRP) Sea un polinomio con deg ( p ) ≥ 0 con coeficientes extraídos de un campo finito G F ( q ) con q un número primo y r una raíz primitiva para ese campo. Determine...
¿Cuáles son los límites conocidos de la capacidad de decisión de la comparación de la tasa de crecimiento de las funciones de ? Estoy aquí pensando en la capacidad de decisión de preguntas como "¿Es x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?" o "¿Es 2 lg ∗ x ∈ O ( lg lg x ) ?".N→NN→N\mathbb{N} \to...
Estoy buscando referencias bibliográficas para el siguiente algoritmo / problema: lo llamé "BiSelect" o "t-ary Select" o "Select in Union of Sorted Arrays", pero supongo que se introdujo antes con otro nombre. Problema Considere el siguiente problema: Dados kkk conjuntos ordenados disjuntos...
Leí el artículo de Freyd "Algebraically Complete Categories" en el famoso Como90 y tengo dos preguntas sobre la noción de compacidad algebraica que definió en ese artículo. (Si no está familiarizado con la definición, aquí está: una categoría se llama algebraicamente compacta si cada endofunctor...