Un estudiante recientemente me pidió que verificara una prueba de dureza NP para ellos. Realizaron una reducción en la línea de: Reduzco este problema P′P′P' que se sabe que es NP completo a mi problema PPP (con una reducción múltiple de tiempo múltiple), por lo que PPP es NP-duro. Mi...
Quiero establecer que esto es parte de mi tarea para un curso que estoy tomando actualmente. Estoy buscando ayuda para proceder, NO UNA RESPUESTA. Esta es la pregunta en cuestión: Una estrella de 5 puntas en un gráfico no dirigido es una camarilla de 5. Muestre esa ESTRELLA DE 5 PUNTOS ∈P∈P\in...
Estoy interesado en el cálculo de la nnn -ésima potencia de un n×nn×nn\times n matriz AAA . Supongamos que tenemos un algoritmo para la multiplicación de matrices que se ejecuta en tiempo O(M(n))O(M(n))\mathcal{O}(M(n)) . Entonces, uno puede calcular fácilmente AnAnA^n en el tiempo...
Sabemos que st-non-connectivityst-non-connectivityst\text{-}non\text{-}connectivity está en NLNL\mathsf{NL} según el teorema del teorema de Immerman – Szelepcsényi y dado que st-connectivityst-connectivityst\text{-}connectivity es NL-hardNL-hard\mathsf{NL\text{-}hard} por lo tanto es un espacio...
Supongamos que se nos dan dos números y y que queremos encontrar para l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r El algoritmo ingenuo simplemente verifica todos los pares posibles; por ejemplo en ruby tendríamos: def max_xor(l, r) max = 0...
Por lo general, Sudoku es , pero esta pregunta se extiende a n 2 × n 2 rompecabezas con n > 3 también. Hay muchas reglas de deducción de tiempo polinomial que pueden avanzar en la búsqueda de una solución para un rompecabezas de Sudoku. Pero a veces, puede ser necesario adivinar valores y seguir...
Dado que la programación lineal entera es NP-completa, hay una reducción de Karp de cualquier problema en NP. Pensé que esto implicaba que siempre hay una formulación de ILP de tamaño polinómico para cualquier problema en NP. Pero he visto documentos sobre problemas específicos de NP en los que la...
Aquí hay un problema bien conocido. Dada una matriz de enteros positivos, genera el entero positivo más pequeño que no esté en la matriz.A[1…n]A[1…n]A[1\dots n] El problema se puede resolver en el espacio y el tiempo : lea la matriz, realice un seguimiento en el espacio O ( n ) si 1 , 2 , … , n...
Me pregunto, ¿cuál es el algoritmo más conocido, en términos de notación Big- , para resolver la programación lineal entera?OOO Sé que el problema es completo, por lo que no espero nada polinomial. Y sé que hay muchas heurísticas y otras que se usan en aplicaciones prácticas como CPLEX, pero estoy...
Estoy tratando de entender la prueba del teorema de Karp-Lipton como se afirma en el libro "Complejidad computacional: un enfoque moderno" (2009). En particular, este libro establece lo siguiente: Teorema de Karp-Lipton Si NP , entonces PH .P ∖ p o l y⊆⊆\subseteq P∖polyP∖polyP_{\backslash...
Me pregunto sobre la relación entre la complejidad computacional y la jerarquía de Chomsky, en general. En particular, si sé que algún problema es NP-completo, ¿se deduce que el lenguaje de ese problema no está libre de contexto? Por ejemplo, el problema de la camarilla es NP-completo. ¿Se deduce...
Tengo varias preguntas relacionadas sobre estos dos temas. En primer lugar, la mayoría de los textos de complejidad sólo pasan por alto la clase NCNC\mathbb{NC} . ¿Existe un buen recurso que cubra la investigación más en profundidad? Por ejemplo, algo que discute todas mis preguntas a...
Estoy seguro de que alguien ha pensado en esto antes o lo descartó de inmediato, pero ¿por qué la teoría de la dicotomía de Schaefer junto con el teorema de Mahaney sobre conjuntos dispersos no implican P = NP? Aquí está mi razonamiento: crear un lenguaje que sea igual a SAT intersectado por un...
ej. ?xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) Las expresiones son del álgebra ordinaria de la escuela secundaria, pero están restringidas a la suma y multiplicación aritmética (por ejemplo, ), sin inversos, restas o divisiones. Las letras son variables.2+2=4;2.3=62+2=4 4;2.3=6 62+2=4;...
Si lo entiendo correctamente, un algoritmo que calcula el valor de una función real tiene una complejidad computacional si se cumple lo siguiente: Cuando calculamos con precisión requiere del orden de pasos .fffO(g(n))O(g(n))O(g(n))fffδδ\deltag(n)g(n)g(n) Sin embargo, ¿qué sucede si tenemos un...
Si de hecho es igual a N P , ¿cómo mejoraría esto nuestros algoritmos para factorizar enteros más rápido? En otras palabras, ¿qué tipo de información nos daría este hecho para comprender mejor la factorización de enteros?PP{\sf P}NPNP{\sf
He estado mirando este sitio y dice que la gente encontró soluciones para recorridos TSP que son solo 0.031% más altos que el recorrido óptimo. Sin encontrar el recorrido óptimo, ¿cómo saben qué longitud se supone que debe
Problema Dada una máquina de Turing que ha conocido el tiempo de ejecución O ( g ( n ) ) con respecto a la longitud de entrada n , ¿es el tiempo de ejecución de M ∈ O ( f ( n ) ) ?MMMO(g(n))O(g(n)){O}(g(n))nnnM∈O(f(n))M∈O(f(n))M \in {O}(f(n)) Es la decidable problema anterior para algunos...
Sé que podemos minimizar los DFA al encontrar y fusionar estados equivalentes, pero ¿por qué no podemos hacer lo mismo con los NFA? No estoy buscando una prueba ni nada de eso, a menos que una prueba sea más fácil de entender. Solo quiero entender intuitivamente por qué la minimización de NFA es...
Para medir la complejidad de un algoritmo, ¿es la complejidad del tiempo o la complejidad computacional? ¿Cuál es la diferencia entre ellos? Solía calcular el recuento máximo (peor) de la operación básica (más costosa) en el