Lo siento si esta pregunta tiene alguna respuesta trivial que me falta. Cada vez que estudio algún problema que se ha demostrado que es indecidible, observo que la prueba se basa en una reducción a otro problema que se ha demostrado que es indecidible. Entiendo que crea algún tipo de orden sobre el...
Según el artículo de Wikipedia sobre esquemas de aproximación de tiempo polinomial : Todos los problemas en FPTAS son manejables de parámetros fijos. Este resultado me sorprende: estas clases parecen ser totalmente diferentes entre sí. FPTAS caracteriza los problemas por su facilidad de...
El problema de decisión Dada una fórmula booleana , ¿tiene exactamente una asignación satisfactoria?ϕϕϕ\phiϕϕ\phi puede verse en , -hard y -hard. ¿Se sabe algo más sobre su complejidad?U P c o N
Estoy trabajando en algoritmos de búsqueda de cadenas que admiten la búsqueda de patrones múltiples. Encontré dos algoritmos que parecen ser los candidatos más fuertes en términos de tiempo de ejecución, a saber, Aho-Corasick y Rabin-Karp . Sin embargo, no pude encontrar ninguna comparación...
Estoy leyendo Sipser y me resulta difícil entender cuál es el proceso, de modo que si me das k máquinas Turing con k cintas, puedo escupir una máquina Turing equivalente con una sola cinta. Un ejemplo sería bueno. En realidad, lo que realmente estoy buscando es un ejemplo resuelto que muestre cómo...
¡Acabo de comenzar a estudiar Inteligencia Artificial y me pregunto por qué el espacio de estado alcanzable de un 8 rompecabezas es 9!/29!/29!/2 . ¡Veo que el número de permutaciones de las fichas es 9!9!9!pero no es inmediatamente obvio por qué la mitad de los posibles estados del rompecabezas son...
¿Existe un algoritmo / procedimiento sistemático para evaluar si un idioma es regular? En otras palabras, dado un idioma especificado en forma algebraica (piense en algo como ), pruebe si el idioma es regular o no. Imagine que estamos escribiendo un servicio web para ayudar a los estudiantes con...
¿Cómo abordaría el problema de la mochila en una situación de programación dinámica si ahora tiene que limitar el número de elementos en la mochila por una constante ? Este es el mismo problema (peso máximo de , cada artículo tiene un valor peso ) pero solo puede agregar artículo (s) a la mochila y...
Sea nnn un número entero y ZZ\mathbb{Z} denote el conjunto de todos los enteros. Supongamos que [a,b][a,b][a,b] denota el intervalo de enteros {a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} . Busco a una estructura de datos para representar un mapa f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} ....
Estoy interesado en las propiedades de una clase de gráficos bipartitos donde todos los nodos en X son 3-regulares, todos los nodos en Y son 2-regulares, y | X | = | 2 Y / 3 | . Primero, ¿es esta una clase de gráficos bien conocida? En segundo lugar,G ( X∪ Y, E)G(X∪Y,E)G(X \cup Y, E)XXXYYYEl | XEl...
Tengo un problema y supongo que es NP-hard, pero no puedo probarlo. Aquí hay un gráfico de capas, donde la capa 0 es la capa más alta y la capa L la más baja. hay un borde dirigido entre capas, donde un borde (A, B) indica que el nodo A puede [cubrir] el nodo B. Y cuando A puede cubrir B, cada...
Los lenguajes sin contexto no se cierran bajo complementación. En las conferencias se nos ha dado el mismo argumento que aquí en Wikipedia : para A={anbncm; m,n∈N0}andB={ambncn; m,n∈N0},A={anbncm; m,n∈ℕ0}andB={ambncn; m,n∈ℕ0},A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈...
Dados dos conjuntos de cadenas sobre el alfabeto , ¿podemos calcular el autómata determinista de estado finito (DFA) más pequeño de modo que y ?A , BUN,siA,BΣΣ\SigmaMETROMETROMA ⊆ L ( M)UN⊆L(METRO)A \subseteq L(M)L ( M) ⊆ Σ∗∖ BL(METRO)⊆Σ∗∖siL(M) \subseteq \Sigma^*\setminus B En otras palabras,...
Estoy involucrado en un curso de programación y algoritmos de primer año. En una conferencia reciente, decidí presentar el material usando codificación en vivo , lo que esencialmente significaba que me sentaba detrás del teclado y escribía código y lo evaluaba, usando emacs para facilitar el...
Leí varias veces que no es posible cambiar la respuesta de un NDTM de manera eficiente. Sin embargo, no entiendo por qué. Por ejemplo, dado un NDTM que se ejecuta en O ( n ) , este texto (sección 3.3) establece que no está claro cómo otro NDTM T puede determinar en O ( n 100 ) tiempo cómo voltear...
Se nos presentó en clase un algoritmo para encontrar el máximo en una matriz en paralelo en O(1)O(1)O(1) complejidad de tiempo con n2n2n^2 computadoras. El algoritmo fue: Dado un conjunto A de longitud n: Haga una matriz B de longitud n e inicialícela con ceros con nnn computadoras....
Minimizar los autómatas finitos deterministas (DFA) es un problema que se ha estudiado a fondo en la literatura, y se han propuesto varios algoritmos para resolver el siguiente problema: Dado un DFA , calcule un DFA mínimo correspondiente que acepte el mismo lenguaje que . La mayoría de estos...
He visto máquinas turing representadas con cintas infinitas en una y en dos direcciones. ¿Hay alguna diferencia en el poder de tales máquinas de turing, o son básicamente equivalentes? En mi cabeza, creo que son equivalentes, ya que supongo que debe haber alguna forma de representar la cinta...
¿Cuántas operaciones aritméticas se requieren para encontrar una matriz pseudoinversa de Moore-Penrose de un campo arbitrario? Si la matriz es invertible y tiene un valor complejo, entonces es solo lo inverso. Encontrar el inverso toma tiempo , donde es la constante de multiplicación de la...
Esta es una especie de pregunta de edición de distancia, y es muy fácil. Estoy completamente muerto de cerebro sobre este tema y no puedo entenderlo hasta ahora. Dada una serie de números, por ejemplo [3, 1, 1, 1] ¿Cómo podría uno convertir más eficientemente todos los números en el mismo...