Dada una enorme base de datos de palabras permitidas (ordenadas alfabéticamente) y una palabra, encuentre la palabra de la base de datos que esté más cerca de la palabra dada en términos de distancia de Levenshtein. El enfoque ingenuo es, por supuesto, simplemente calcular la distancia levenshtein...
Dados subconjuntos de .S 1 , ... , S n { 1 , ... , d }nnnS1,…,SnS1,…,SnS_1,\ldots,S_n{1,…,d}{1,…,d}\{1,\ldots,d\} Compruebe si hay conjuntos con . (Si es así, encuentre un ejemplo, si no, simplemente diga "no")Si,SjSi,SjS_i,S_jSi⊊SjSi⊊SjS_i \subsetneq S_j La solución trivial a este problema pasa...
Sé que es indecidible determinar si un conjunto de fichas puede enlosar el plano, como resultado de que Berger usa fichas de Wang . Mi pregunta es si también se sabe que es indecidible determinar si un solo mosaico dado puede enlosar el plano, un mosaico monoédrico . Si esto sigue sin resolverse,...
Actualmente, bitcoin tiene un sistema de prueba de trabajo (PoW) que usa SHA256. Otras funciones hash utilizan una prueba de gráficos de uso del sistema de trabajo, inversión parcial de la función hash. ¿Es posible usar un problema de Decisión en la teoría de nudos como el reconocimiento de nudos...
¿Alguien puede sugerir una encuesta buena y reciente sobre problemas de conteo y / o problemas que son #P.
Es posible que algunos de ustedes hayan estado siguiendo esta pregunta , que se cerró debido a que no tenía nivel de investigación. Entonces, estoy extrayendo la parte de la pregunta que está a nivel de investigación. Más allá de las técnicas "más simples", como reducir a la clasificación o un...
El problema No todos iguales -SAT (NAE k -SAT), dado un conjunto C de cláusulas sobre un conjunto X de variables booleanas de modo que cada cláusula contenga como máximo k literales, pregunta si existe una asignación de verdad de las variables de manera que cada cláusula contiene al menos un...
Estoy tratando de entender la relación entre el isomorfismo gráfico y el problema oculto de subgrupos. ¿Hay una buena referencia para
Estoy interesado en el problema de empacar copias idénticas de rectángulos (2 dimensiones) en un polígono convexo (2 dimensiones) sin superposiciones. En mi problema, no puede rotar los rectángulos y puede suponer que están orientados en paralelo con los ejes. Solo se le dan las dimensiones de un...
Para un alfabeto finito fijo , un lenguaje formal sobre es normal si existe un autómata finito determinista (DFA) sobre que acepta exactamente .L Σ Σ LΣΣ\SigmaLLLΣΣ\SigmaΣΣ\SigmaLLL Me interesan los idiomas que son "casi" regulares en el sentido de que pueden ser reconocidos por las familias de...
He leído en innumerables artículos que determinar la constante Cheeger de un gráfico es -duro. Parece ser un teorema popular, pero nunca he encontrado ni una cita ni una prueba de esta afirmación. ¿A quién debo dar crédito por ello? En un documento antiguo (Isoperimetric Numbers of Graphs, J. Comb....
Para una constante , se puede determinar en tiempo lineal, dado un gráfico de entrada G , si su ancho de árbol es ≤ k . Sin embargo, cuando k y G se dan como entrada, el problema es NP-hard. ( Fuente )k ∈ Nk∈Nk \in \mathbb{N}solGG≤ k≤k\leq kkkksolGG Sin embargo, cuando el gráfico de entrada es...
Actualmente estoy tratando de encontrar problemas completos de EXPSPACE (principalmente para encontrar inspiración para una reducción), y estoy sorprendido por la pequeña cantidad de resultados que se presentan. Hasta ahora, encontré estos, y tengo problemas para expandir la lista: universalidad...
La teoría de la complejidad, a través de conceptos como la completitud de NP, distingue entre problemas computacionales que tienen soluciones relativamente eficientes y aquellos que son intratables. La complejidad "de grano fino" tiene como objetivo refinar esta distinción cualitativa en una guía...
Esta pregunta es sobre la complejidad temporal del algoritmo de flujo máximo de Ford-Fulkerson cuando se usa DFS para encontrar rutas de aumento. Hay un ejemplo bien conocido que muestra que el uso de DFS puede necesitar un número lineal de iteraciones en el flujo máximo; consulte, por ejemplo, la...
Me preguntaba qué documentos debería leer para entender esta pregunta Una conexión inesperada con otras áreas de las matemáticas, como la geometría algebraica o la cohomología superior. Quizás incluso un área de matemáticas aún no desarrollada. Quizás alguien desarrolle una dirección...
Un tensor es una generalización de vectores y matrices a dimensiones superiores y el rango de un tensor también generaliza el rango de una matriz. A saber, el rango de un tensor es el número mínimo de rango uno tensores que suma a T . Un vector y una matriz son tensores de grado 1 y 2...
Al jugar con el análisis LR no canónico, pensé en un método de análisis (con tablas de tamaño infinito, lo que lo hace poco práctico ) capaz de analizar exactamente las gramáticas inequívocas en el tiempo , y me preguntaba si es posible hacerlo mejor :O ( n2)O(norte2)O(n^2) ¿Se pueden analizar...
¿Alguien sabe de referencias que explican con precisión la conexión entre el algoritmo de unificación y la eliminación gaussiana? Estoy particularmente interesado en la relación entre las sustituciones triangulares y las descomposiciones LU. Wayne Snyder y Jean Gallier mencionan esta analogía de...
Me acabo de dar cuenta de que he estado asumiendo que la respuesta a mi pregunta es "sí", pero no tengo una buena razón. Me imagino que tal vez haya un recolector de basura que probablemente solo presente peor desaceleración. ¿Hay alguna referencia definitiva que pueda citar? En mi caso, estoy...