La etiqueta de imagen grande es para una "visión general amplia o perspectiva de un problema o problema".
Para demostrar la importancia de los algoritmos (por ejemplo, para estudiantes y profesores que no hacen teoría o incluso son de campos completamente diferentes), a veces es útil tener a mano una lista de ejemplos en los que se han implementado algoritmos centrales en empresas comerciales,...
He estado revisando Theory of Computation por diversión y esta pregunta me ha estado molestando por un tiempo (curioso, nunca lo pensé cuando aprendí Automata Theory en mi licenciatura). Entonces, ¿por qué exactamente estudiamos autómatas finitos deterministas y no deterministas (DFA / NFA)? Así...
Solo estoy leyendo sobre el cálculo lambda para "conocerlo". Lo veo como una forma alternativa de cálculo en lugar de la máquina de Turing. Es una forma interesante de hacer cosas con funciones / reducciones (hablando en términos generales). Sin embargo, algunas preguntas me siguen...
Los matemáticos a veces se preocupan por el Axioma de Elección (AC) y el Axioma de Determinación (AD). Axioma de elección : Dado cualquier colección de conjuntos no vacíos, hay una función f que, dado un conjunto S en C , devuelve un miembro de S .CC{\cal C}fffSSSCC{\cal C}SSS Axioma de...
Soy un profesional del software y estoy escribiendo una encuesta sobre estructuras algebraicas para la investigación personal y estoy tratando de producir ejemplos de cómo se utilizan estas estructuras en la informática teórica (y en menor grado, otros subcampos de la informática) . Bajo la teoría...
En la actualidad, no es factible resolver un problema completo o un problema completo P S P A C E en el caso general de entradas grandes. Sin embargo, ambos se pueden resolver en tiempo exponencial y espacio polinómico.nortePAGSNPNPPAGSSPAGSA CmiPSPACEPSPACE Dado que no podemos construir...
Mi pregunta hoy es (como siempre) un poco tonta; pero le pediría que lo considere amablemente. Quería saber sobre la génesis y / o motivación detrás del concepto de ancho de árbol. Estoy seguro de que entiendo que se usa en algoritmos FPT, pero no creo que esa sea la razón por la que se definió...
Recientemente, cuando hablé con un físico, afirmé que, en mi experiencia, cuando un problema que ingenuamente parece que debería llevar un tiempo exponencial resulta no trivial en P o BPP, generalmente se puede identificar una "razón general" por la que ocurre la reducción. --- y casi siempre, esa...
Me he encontrado con el algoritmo polinómico que resuelve 2SAT. Me ha parecido sorprendente que 2SAT esté en P, donde todas (o muchas otras) de las instancias de SAT son NP-Complete. ¿Qué hace que este problema sea diferente? ¿Qué lo hace tan fácil (NL-Complete, incluso más fácil que...
Hay algunos problemas de conteo que implican contar exponencialmente muchas cosas (en relación con el tamaño de la entrada) y, sin embargo, tienen sorprendentes algoritmos deterministas exactos de tiempo polinómico. Ejemplos incluyen: Contar combinaciones perfectas en un gráfico plano (el...
Esta podría ser una pregunta subjetiva en lugar de una con una respuesta concreta, pero de todos modos. En teoría de la complejidad estudiamos la noción de cálculos eficientes. Hay clases como representa el tiempo polinómico y representa el espacio de registro . Se considera que ambos están...
Permítanme comenzar con algunos ejemplos. ¿Por qué es tan trivial mostrar que CVP está en P pero tan difícil de mostrar que LP está en P? mientras que ambos son problemas P-completos. O toma la primalidad. Es más fácil mostrar compuestos en NP que primos en NP (que requirieron Pratt) y...
La jerarquía de Chomsky (–Schützenberger) se usa en los libros de texto de informática teórica, pero obviamente solo cubre una fracción muy pequeña de lenguajes formales (REG, CFL, CSL, RE) en comparación con el Diagrama completo del zoológico de complejidad . ¿La jerarquía juega algún papel en la...
En un hilo diferente , Andrej Bauer definió la semántica denotacional como: El significado de un programa es una función de los significados de sus partes. Lo que me molesta de esta definición es que no parece distinguir lo que comúnmente se considera semántica denotacional de lo que...
Las computadoras reales tienen memoria limitada y solo un número finito de estados. Por lo tanto, son esencialmente autómatas finitos. ¿Por qué los informáticos teóricos usan las máquinas de Turing (y otros modelos equivalentes) para estudiar computadoras? ¿Cuál es el punto de estudiar estos...
El campo de la computación distribuida se ha quedado lamentablemente corto en el desarrollo de una sola teoría matemática para describir algoritmos distribuidos. Existen varios 'modelos' y marcos de cómputo distribuido que simplemente no son compatibles entre sí. La gran explosión de propiedades...
Ryan Williams acaba de publicar su límite inferior en ACC , la clase de problemas que tienen circuitos de profundidad constante con ventiladores y puertas ilimitadas AND, OR, NOT y MOD_m para todos los m posibles. ¿Qué tienen de especial las puertas MOD_m? Permiten simular aritmética sobre...
Se cree comúnmente que para todo , es posible multiplicar dos matrices en el tiempo . Alguna discusión está aquí .ϵ > 0ϵ>0\epsilon > 0n × nn×nn \times nO ( n2 + ϵ)O(n2+ϵ)O(n^{2 + \epsilon}) Le pregunté a algunas personas que están más familiarizadas con la investigación si creen que hay un...
A veces se afirma que la Teoría de la Complejidad Geométrica de Ketan Mulmuley es el único programa plausible para resolver las preguntas abiertas de la teoría de la complejidad como la pregunta P vs. NP. Ha habido varios comentarios positivos de famosos teóricos de la complejidad sobre el...
En su libro "Complejidad computacional", Papadimitriou escribe: RP es, en cierto sentido, un tipo nuevo e inusual de clase de complejidad. Ninguna máquina de Turing no determinista limitada polinómicamente puede ser la base para definir un lenguaje en RP. Para que una máquina N defina un...