Estoy pensando en el siguiente problema: quiero encontrar una expresión regular que coincida con un conjunto particular de cadenas (por ejemplo, direcciones de correo electrónico válidas) y que no coincida con otras (direcciones de correo electrónico no válidas). Supongamos que por expresión...
¿Alguien puede proporcionar una explicación concisa del enfoque GCT de Mulmuley comprensible para los no expertos? Una explicación que sería adecuada para una página de Wikipedia sobre el tema (que es un trozo en este momento). Motivación: estoy "co-leyendo" el libro de computación cuántica de...
Si pudieras cambiar el nombre de la programación dinámica, ¿cómo lo
¿Hay algún beneficio en el cálculo de la complejidad temporal de un algoritmo que utiliza cálculo lambda? ¿O hay otro sistema diseñado para este propósito? Cualquier referencia sería
En otro hilo , Joe Fitzsimons preguntó sobre "los mejores límites inferiores actuales en 3SAT". Me gustaría ir a otro lado: ¿Cuál es el mejor límite superior actual en 3SAT? En otras palabras, ¿cuál es la complejidad temporal del solucionador SAT más eficiente? En particular, ¿es concebible...
Parece claro que varios subcampos de la informática teórica se han visto significativamente afectados por los resultados de la física teórica. Dos ejemplos de esto son Computación cuántica Resultados de mecánica estadística utilizados en análisis de complejidad / algoritmos...
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...
Actualmente estoy escribiendo una encuesta sobre teoremas de jerarquía en TCS. Al buscar artículos relacionados, noté que la jerarquía es un concepto fundamental no solo en TCS y matemáticas, sino en numerosas ciencias, desde teología y sociología hasta biología y química. Al ver que la cantidad de...
Inspirado por esta pregunta y en particular el párrafo final de la respuesta de Or, tengo la siguiente pregunta: ¿Conoces alguna aplicación de la teoría de la representación del grupo simétrico en TCS? El grupo simétrico es el grupo de todas las permutaciones de con composición de operación de...
En MathOverflow, Timothy Gowers hizo una pregunta titulada " Demostrar que el rigor es importante ". La mayor parte de la discusión allí fue sobre casos que muestran la importancia de la prueba, de los cuales las personas en CSTheory probablemente no necesitan estar convencidos. En mi experiencia,...
Soy un estudiante graduado de segundo año en teoría. He estado trabajando en un problema durante el último año (en teoría de gráficos / algoritmos). Hasta ayer pensé que me estaba yendo bien (estaba ampliando un teorema de un artículo). Hoy me di cuenta de que he cometido un simple error. Me di...
En 1937, Turing describió una máquina de Turing. Desde entonces, se han descrito muchos modelos de computación en un intento de encontrar un modelo que sea como una computadora real pero que sea lo suficientemente simple como para diseñar y analizar algoritmos. Como resultado, tenemos una docena...
A pesar de varios años de clases, todavía estoy perdido cuando se trata de elegir un tema de investigación. He estado revisando documentos de diferentes áreas y hablado con profesores, y estoy empezando a pensar que este es el enfoque equivocado. He leído que ayuda a encontrar un problema...
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...
Mi pregunta es simple: ¿Cuál es el peor tiempo de ejecución del algoritmo más conocido para calcular una descomposición propia de una matriz n × nnorte×norten \times n ? ¿La descomposición propia se reduce a la multiplicación matricial o son los algoritmos más conocidos O ( n3)O(norte3)O(n^3)...
Esta es una pregunta relacionada con esta . Poniéndolo de nuevo en una forma mucho más simple después de mucha discusión allí, se sintió como una pregunta totalmente diferente. La prueba clásica de la indecidibilidad del problema de detención depende de demostrar una contradicción cuando se trata...
Fondo El cálculo sobre números reales es más complicado que el cálculo sobre números naturales, ya que los números reales son objetos infinitos y hay innumerables números reales, por lo tanto, los números reales no pueden representarse fielmente por cadenas finitas sobre un alfabeto finito. A...
Esta es una pregunta sobre la complejidad del circuito. (Las definiciones están en la parte inferior). Yao y Beigel-Tarui mostraron que cada familia de circuitos de tamaño tiene una familia de circuitos equivalente de tamaño de profundidad dos , donde la puerta de salida es una función simétrica y...
El problema del isomorfismo gráfico (IG) es posiblemente el candidato más conocido para un problema NP-intermedio . El algoritmo más conocido es el algoritmo sub-exponencial con tiempo de ejecución . Se sabe que GI no esNP-completo a menos que lajerarquía polinómica secolapse.2O ( n...
Me gustaría entender Applicativeen términos de teoría de categorías. La documentación de Applicativedice que es un functor monoidal fuerte y laxo . Primero, la página de Wikipedia sobre los functores monoidales dice que un functor monoidal es laxo o fuerte . Entonces, me parece que una de las...