Definir un "problema" a ser un algoritmo aceptar un número natural y devolver 0 o 1 que devuelve 1 en al menos un n ∈ N . Cualquiera de tales n se llama una "solución" a AAAA111n∈Nn∈Nn \in \mathbb{N}nnnAAA Defina un "solucionador de problemas universal" como un algoritmo acepta un problema y...
Dado un gráfico dirigido con n nodos de modo que cada vértice tenga exactamente dos bordes salientes, y un número natural N codificado en binario, dos vértices syt, Quiero contar el número de rutas (no necesariamente simples) de sa t en N pasos. ¿Es este un problema difícil de # P? O, en...
Ahora se sabe que el adversario general de límite inferior caracteriza la complejidad de la consulta cuántica debido al trabajo innovador de Reichardt et al. La misma línea de trabajo también establece conexiones con el marco del programa span para diseñar algoritmos cuánticos. Muchos algoritmos...
Si nos dan dos cadenas de tamaño y n 2 , la Levenshtein cálculo de distancia de edición estándar es mediante un algoritmo dinámico con el tiempo complejidad O ( n 1 n 2 ) y el espacio complejidad O ( n 1 n 2 ) . (Se pueden hacer algunas mejoras en función de la distancia de edición d , pero no...
Se han realizado algunos esfuerzos para atacar el problema del isomorfismo gráfico utilizando la caminata aleatoria cuántica de bosones de núcleo duro (simétrica pero sin ocupación doble). Amir Rahnamai Barghi e Ilya Ponomarenko demostraron que el poder simétrico de la matriz de adyacencia, que...
ETH afirma que SAT no se puede resolver en el peor de los casos en tiempo subexponencial. ¿Qué pasa con el caso promedio? ¿Hay problemas naturales en NP que se supone que son exponencialmente difíciles en el caso promedio? Tome el caso promedio como el tiempo promedio de ejecución con una...
Arregle un problema de búsqueda NP-complete, por ejemplo, la forma de búsqueda de SAT. La búsqueda de Levin proporciona un algoritmo para resolver X que es óptimo en algún sentido. Específicamente, el algoritmo es "Ejecutar todos los posibles programas P en cola de milano en la entrada x , una vez...
RP=NPRP=NPRP = NP es ampliamente conjeturado como falso. Pero imagine por un momento que es verdad. En tal caso, ¿qué tan probable sería que ?P=NPP=NPP = NP En otras palabras: en un mundo donde RP=NPRP=NPRP = NP , ¿qué podría verse como un obstáculo para que creamos P=NPP=NPP = NP...
El teorema de la dicotomía de Schaefer muestra que cada problema de CSP sobre puede resolverse en tiempo polinómico o es NP completo. Esto aplica solo para problemas CSP de ancho acotado, excluyendo SAT y Horn-SAT, por ejemplo. Los problemas generales de CSP de ancho ilimitado pueden ser muy...
Estoy buscando resultados de dureza en la coloración de vértices de gráficos con grado acotado. Dado un gráfico , sabemos que para cualquier ϵ > 0 , es difícil aproximar χ ( G ) dentro de un factor de | V | 1 - ϵ a menos que NP = ZPP [ 1 ]. Pero, ¿qué pasa si el grado máximo de G está limitado...
Sudoku es un rompecabezas bien conocido que es NP completo. Sudoku binario es una variante que solo permite los números y 1 . Las reglas son las siguientes.000111 Cada fila y cada columna deben contener un número igual de ceros y unos. Cada fila y cada columna es única. Ninguna fila o columna...
Defina como la clase de idiomas que puede aceptar una máquina de Turing (multitapa) en el tiempo f ( n ) + 1 . (El " + 1 " es simplemente para simplificar la notación y evitar confusiones). Observe que no hay O ( ⋅ ) alrededor de f ( n ) + 1
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
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 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...
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...