La historia detrás de los temas: de dónde viene su nombre, quién los descubrió, cuándo se probaron por primera vez, cómo evolucionaron durante los años.
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...
Esta es una "pregunta histórica" más de lo que es una pregunta de investigación, pero ¿fue la reducción clásica a la búsqueda de orden en el algoritmo de factorización de Shor inicialmente descubierta por Peter Shor, o se sabía previamente? ¿Existe algún documento que describa la reducción...
Me gustaría escribir una encuesta sobre las aplicaciones de la topología en informática. Planeo cubrir la historia de las ideas topológicas en Ciencias de la Computación y también destacar algunos desarrollos actuales. Sería extremadamente útil si alguien pudiera dar su opinión sobre cualquiera de...
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ó...
Tengo entendido que el modelo de Turing se ha convertido en el "estándar" al describir el cálculo. Me interesa saber por qué este es el caso, es decir, por qué el modelo TM se ha vuelto más utilizado que otros modelos teóricamente equivalentes (que yo sepa), por ejemplo, μ-Recursion de Kleene o el...
Si pudieras cambiar el nombre de la programación dinámica, ¿cómo lo
En el clásico artículo de 1979 de Andrew Chi-Chih Yao, hace referencia a "MO Rabin y AC Yao, en preparación". Esto es por el resultado de que la complejidad de la comunicación de error acotado de la función de igualdad EQ N (si dos enteros en el rango de 0 a N - 1 son iguales) es O ( log log N )...
Este problema está inspirado en esta pregunta de MO , que me pareció muy interesante. ¿Cuál es el problema abierto más antiguo en TCS? Claramente esta pregunta necesita alguna aclaración. Primero, ¿qué es TCS? Creo que la existencia de números perfectos impares no es TCS. Yo diría que el...
Alan Turing , uno de los pioneros de la informática (teórica), hizo muchas contribuciones científicas seminales a nuestro campo, incluida la definición de máquinas de Turing, la tesis de Church-Turing, la indecidibilidad y la prueba de Turing. Sin embargo, sus descubrimientos importantes no se...
Tengo una pregunta historica. Estoy tratando de determinar la referencia para el hecho de que la capacidad de coloración en 3 de los gráficos (alternativamente, la capacidad de coloración en para k ≥ 3 dada ) es NP-difícil.kkkk≥3k≥3k\geq 3 La respuesta tentadora es "el documento original de...
"Sabemos" que lleva el nombre de Steve Cook y N C lleva el nombre de Nick Pippenger. Si no me equivoco, Steve Cook nombró a NC en honor a Nick Pippenger, y me dijeron que lo contrario también es cierto. Sin embargo, no he podido encontrar ninguna evidencia de este último hecho en el documento de...
En un par de preguntas recientes ( q1 q2 ), se ha debatido sobre "Teoría A" versus "Teoría B", aparentemente para capturar la división entre el estudio de los lenguajes de lógica y programación y el estudio de algoritmos y complejidad. Esta terminología era nueva para mí, y una búsqueda rápida en...
En su libro, Boolean Function Complexity, Stasys Jukna menciona (página 564) que Kolmogorov creía que cada lenguaje en P tiene circuitos de tamaño lineal. No se menciona ninguna referencia y no pude encontrar nada en línea. ¿Alguien sabe más sobre
¿Por qué los lenguajes regulares (y de esas expresiones regulares) se llaman "regulares"? Hay mucha regularidad también en los idiomas sin contexto de otros tipos de idiomas. Supongo que, al principio, el adjetivo "regular" se ha utilizado para diferenciar ese tipo de idiomas de otros lenguajes...
Grothendieck ha fallecido . Tuvo un impacto masivo en las matemáticas del siglo XX que continuaron hasta el siglo XXI. Esta pregunta se hace algo en el estilo / espíritu, por ejemplo, de las Contribuciones de Alan Turing a la informática . ¿Cuáles son las principales influencias de Grothendieck...
Editar: elijo la respuesta con la puntuación más alta antes del 06 de diciembre de 2012. Esta es una pregunta suave. El concepto de algoritmos (deterministas) se remonta a BC. ¿Qué pasa con los algoritmos probabilísticos? En esta entrada de la wiki , el algoritmo de Rabin para el problema de par...
Si es un gráfico d- no dirigido y S es un subconjunto de los vértices de la cardinalidad ≤ | V | / 2 , llame a la expansión del borde de S la cantidadG = ( V, E)G=(V,E)G=(V,E)reddSSS≤ | VEl | / 2≤|V|/2\leq |V|/2SSS ϕ ( S) : = Eresole s ( S, V- S)re⋅ | SEl | ⋅ | V- SEl...
Los otros editores sabios de Wikipedia han rechazado mi solicitud de mover el artículo de Wikipedia sobre el algoritmo Rabin-Karp a lo que creo que debería llamarse, el algoritmo Karp-Rabin, sobre la base de que el nombre Rabin-Karp se usa con más frecuencia ( falso, si uno usa los números de...
Estoy seguro de que todos conocen el experimento de la aguja de Buffon en el siglo XVIII, que es uno de los primeros algoritmos probabilísticos para calcular .ππ\pi La implementación del algoritmo en las computadoras generalmente requiere el uso de , o una función trigonométrica, que, incluso si...
Recientemente enseñé expansores e introduje la noción de gráficos Ramanujan. Michael Forbes preguntó por qué se les llama así, y tuve que admitir que no lo sé.