Estoy buscando recursos (preferiblemente un manual) sobre temas avanzados en algoritmos (temas más allá de lo que se cubre en los libros de texto de algoritmos como CLRS y DPV). El tipo de material que se puede usar para enseñar un tema en un curso de algoritmos como Erik Demaine y el curso de...
La única definición de "cálculo" que conozco es el estudio de límites, derivados, integrales, etc. en el análisis. ¿En qué sentido es el cálculo lambda (o cosas como el cálculo mu) un "cálculo"? ¿Cómo se relaciona con el cálculo en el
La clase UP se define como tal: La clase de problemas de decisión que una máquina NP puede resolver Si la respuesta es 'sí', se acepta exactamente una ruta de cálculo. Si la respuesta es 'no', todas las rutas de cálculo se rechazan. Estoy tratando de desarrollar la intuición para esta...
El problema de la "Segunda " es el problema de decidir la existencia de otra solución diferente de alguna solución dada para la instancia del problema.XXX Para algunos problemas de -completo, la segunda versión de la solución es N P -completa (decidir la existencia de otra solución para el...
Impagliazzo, Paturi y Calabro, Impagliazzo, Paturi introdujeron la hipótesis del tiempo exponencial (ETH) y la hipótesis del tiempo fuertemente exponencial (SETH). Aproximadamente, SETH dice que no existe un algoritmo que resuelva SAT en el tiempo . 1.99n1.99n1.99^n Me preguntaba qué significaría...
Estoy buscando una clase de complejidad que se relacione con APX como BPP se relaciona con P. Ya he hecho la misma pregunta aquí , pero tal vez TCS sería una ubicación más fructífera para las respuestas. La razón de la pregunta es que, en problemas prácticos, a menudo es necesario encontrar...
¿Conoces problemas que son W [1] -duros incluso para gráficos de grados acotados? La dimensión métrica es difícil en gráficos con un grado máximo de 3, pero es W [2] -duro. Red-Blue Nonblocker solía ser W [1] duro en gráficos de grados limitados, pero hubo un error en la prueba (libro de Downey...
¿Existe una forma documentada de calcular nudos? (circunferencias incrustadas en un espacio euclidiano tridimensional). Quiero decir, un tipo de datos para representarlos y un algoritmo para determinar si dos instancias del tipo de datos representan el mismo nudo. Si la respuesta es positiva,...
¿Se conoce el siguiente reclamo? Reclamación : Para cualquier gráfico con n vértices existe una coloración de G tal que cada conjunto independiente está coloreado como máximo por O ( √solGGnortennsolGGcolores.O (
Tengo una pregunta sobre las funciones puras. Según la página de Wikipedia, uno de los requisitos para una función pura es: La evaluación del resultado no causa ningún efecto secundario o salida semánticamente observable, como la mutación de objetos mutables o la salida a dispositivos de E /...
Hasta donde sé, la norma de factorización del límite inferior dada por Linial y Shraibman es esencialmente el único límite inferior conocido para la complejidad de la comunicación cuántica (o al menos subsume todos los demás). ¿Hay alguna evidencia en contra de que este límite sea estricto? La...
En teoremas gratis! , Wadler dice que la caracterización de la parametricidad se puede volver a expresar en términos de transformaciones naturales laxas y este será el tema de otro artículo. ¿A qué papel se refiere? El enfoque categórico de la paramtericidad que conozco utiliza transformaciones...
Un gráfico plano es un gráfico que se puede incrustar en el plano, sin tener bordes cruzados. Supongamos que sea una hipergrafía k -uniforme, es decir, una hipergrafía tal que todas sus hiperedificaciones tengan el tamaño k.G=(X,E)G=(X,E)G=(X,E)kkk Se han realizado algunos trabajos para...
Después de leer una pregunta relacionada , acerca de las pruebas de algoritmos de existencia no constructivas, me preguntaba si existen métodos para mostrar la existencia de máquinas de cómputo "pequeñas" (por ejemplo, a nivel de estado) sin construirlas realmente. Formalmente: supongamos que...
La teoría de tipos de Martin-Löf usa tipos W para definir estructuras inductivas como enteros, listas, etc. Sin embargo, el cálculo de construcciones inductivas no las usa de la misma manera, los tipos inductivos parecen ser más como esquemas de axiomas. ¿Son equivalentes estos dos enfoques...
Denote por el grado mínimo de salida en G , y por δ - ( G ) el grado mínimo de entrada.δ+(G)δ+(G)\delta^+(G)GGGδ−(G)δ−(G)\delta^-(G) En una pregunta relacionada , mencioné la extensión de Ghouila-Houri del teorema de Dirac sobre los ciclos hamiltonianos , que sugiere que si entonces G es...
Entonces, el problema de la cobertura del conjunto es trivial si ninguno de los conjuntos candidatos se cruza entre sí. Sin embargo, ¿qué pasa si el tamaño de la intersección para cualquier par de conjuntos candidatos era como máximo 1? ¿Es este problema NP-hard? Agradecería cualquier...
Aquí hay un problema con un sabor similar al de las juntas de aprendizaje: Entrada: Una función f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\} , representada por un oráculo de membresía, es decir, un oráculo que dado xxx , devuelve f(x)f(x)f(x) . Objetivo: encontrar un subcubo...
Como mencionó @Marzio, el siguiente juego se conoce como Geografía Generalizada . Dado un gráfico y un vértice inicial , el juego se define de la siguiente manera:v ∈ VG = ( V, E)sol=(V,mi)G=(V,E)v ∈ Vv∈Vv \in V En cada turno (dos jugadores alternando), un jugador elige u ∈ N( v )tu∈norte(v)u\in...
La prueba estándar de que BQPSPACE está en PSPACE se basa en un análisis de tipo de juego Savitch en integrales de ruta. Sin embargo, se supone que el tiempo de ejecución de BQPSPACE es como máximo exponencialmente largo. Esto es cierto para PSPACE, pero para sistemas cuánticos cerrados con un...