Si , entonces es ? Estoy haciendo esta pregunta porque, para otras clases no deterministas, parece que siempre establece que son iguales a sus contrapartes deterministas.P=NPP=NP\mathbf{P} = \mathbf{NP}L=NLL=NL\mathbf{L} = \mathbf{NL}P=NPP=NP\mathbf{P} =
Sé que los lenguajes que se pueden definir usando expresiones regulares y aquellos reconocibles por DFA / NFA (autómatas finitos) son equivalentes. Tampoco existe DFA para el idioma { 0norte1norteEl | n≥0}{0 0norte1norteEl |norte≥0 0}\{0^n1^n|n \ge 0\} . Pero aún así puede escribirse usando...
Dado un conjunto de puntos y un radio r . Cuál es la complejidad de encontrar el punto con mayor número de puntos a una distancia menor que r . Por ejemplo, el que maximiza ∑ n i = 1 1 ‖ x - x i ‖ ≤ r ?x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in
Wikipedia dice que la unión por rango sin compresión de ruta da una complejidad de tiempo amortizada de , y que tanto la unión por rango como la compresión de ruta da una complejidad de tiempo amortizada de O ( α ( n ) ) (donde α es el inverso de Función Ackerman). Sin embargo, no menciona el...
Quiero entender la teoría de tipos, pero primero tengo que saber cómo puedo aplicarla. ¿Podría haber más aplicaciones no obvias de la teoría de tipos aparte de los sistemas de tipos en programación? ¿Podría haber otras aplicaciones, digamos en el perfil de personalidad y los...
Los tipos propios son una extensión del cálculo de construcciones [1] que permiten que el lenguaje exprese tipos de datos algebraicos codificados a través de la codificación Scott. Scott Encoding proporciona a uno la capacidad de combinar patrones O(1), que es uno de los principales motivadores...
Estoy aprendiendo cómo convertir NFA a DFA y quiero asegurarme de que lo estoy haciendo bien. Obviamente, retroceder en la otra dirección no es una cosa. ¿Alguien sabe de un algoritmo para verificar que un DFA es equivalente a un
Descargo de responsabilidad: Sé que hay preguntas similares que suenan aquí y en Stackoverflow. Pero se trata de colisiones, que no es lo que estoy pidiendo. Mi pregunta es: ¿por qué la búsqueda sin colisiones O(1)en primer lugar? Supongamos que tengo esta tabla hash: Hash...
He estado tratando de averiguar si el problema de detención es decidible para autómatas celulares unidimensionales de 3 símbolos. Definición Sea la configuración del sistema en el paso de tiempo . Más formalmente , donde es el alfabeto.i f : A ∗ × N → A ∗
Según mi lectura, parece que la mayoría de las gramáticas se preocupan por generar un número infinito de cadenas. ¿Qué pasa si trabajas al revés? Si se le dan n cadenas de m longitud, debería ser posible hacer una gramática que genere esas cadenas y solo esas cadenas. ¿Existe un método conocido...
Estoy implementando un algoritmo Naive Bayes para la categorización de texto con suavizado laplaciano. El problema que tengo es que la probabilidad se acerca a cero porque estoy multiplicando muchas fracciones pequeñas. Por lo tanto, la probabilidad finalmente produce cero. Esto se debe a que hay...
Escribí este código de Python y me pregunté si a veces simplemente no termina (suponiendo que tengamos memoria / tiempo infinito y ningún límite de profundidad de recursión). Intuitivamente pensarías que termina, ya que en algún momento debes tener suerte , y si no termina tienes una cantidad...
De esta referencia: positividad estricta La condición de positividad estricta descarta declaraciones como data Bad : Set where bad : (Bad → Bad) → Bad A B C -- A is in a negative position, B and C are OK ¿Por qué A es negativo? ¿También por qué B está permitido? Entiendo por qué C está...
Hace poco me enteré de la estructura de datos del árbol de rosas, pero simplemente saliendo de una datadefinición de Haskell y la pequeña descripción de Wikipedia , tengo algunos problemas para entender qué aplicaciones podría tener un árbol de rosas. Como referencia, la datadefinición de Haskell...
No sé la terminología correcta para hacer esta pregunta, así que la describiré con muchas palabras, tengan paciencia conmigo. Antecedentes , solo para estar en la misma página: los programas a menudo contienen cachés, una compensación de tiempo / memoria. El error de un programador común es...
Quiero proporcionar pruebas de partes de un programa de Haskell que estoy escribiendo como parte de mi tesis. Hasta ahora, sin embargo, no pude encontrar un buen trabajo de referencia. El libro introductorio de Graham Hutton Programming in Haskell ( Google Books ), que leí mientras aprendía...
Esta prueba es una prueba por inducción, y es la siguiente: P (n) es la afirmación de que "Quicksort ordena correctamente cada matriz de entrada de longitud n". Caso base: cada matriz de entrada de longitud 1 ya está ordenada (P (1) se mantiene) Paso inductivo: arreglo n => 2. Arregle alguna...
Estoy tratando de enseñarme sobre computación cuántica, y tengo una comprensión decente del álgebra lineal. Atravesé la puerta NOT, que no estaba tan mal, pero luego llegué a la puerta Hadamard. Y me quedé atrapado. Principalmente porque si bien "entiendo" las manipulaciones, no entiendo lo que...
Hoy he aprendido que el análisis de algoritmos difiere según el modelo computacional. Es algo en lo que nunca he pensado ni oído hablar. Un ejemplo que me dio, que lo ilustró aún más, por el usuario @chi fue: Por ejemplo, considere la tarea: dado devuelve . En RAM esto se puede resolver...
Considere una máquina de estados finitos como de costumbre, pero en cada transición, también puede actualizar un contador entero sumando o restando un número. Digamos, una función de transición de la forma mueve al nuevo estado p , y agrega k al contador, donde k ∈ Z (entonces k puede ser...