La solicitud de referencia se utiliza cuando el autor necesita saber sobre el trabajo relacionado con la pregunta.
Desde el libro de 1998 de Chris Okasaki "Estructuras de datos puramente funcionales", no he visto aparecer muchas nuevas estructuras de datos puramente funcionales; Puedo nombrar solo algunos: IntMap (también inventado por Okasaki en 1998, pero no presente en ese libro) Árboles de dedos (y su...
[ Cronología ] Esta pregunta tiene el mismo espíritu de qué documentos deben leer todos y qué videos deben ver todos . Pide libros notables en diferentes áreas de la informática teórica. Los libros pueden estar orientados a las matemáticas, sin embargo, puede ser excelente para un científico de...
Ha habido varias preguntas con el mismo esquema que este: ¿Qué documentos deberían leer todos? ¿Qué libros deberían leer todos? ¿Cuáles son los libros recientes de TCS cuyos borradores están disponibles en línea? ¿Qué videos deberían ver todos? Era reacio a publicar otro más, pero las notas de...
La informática teórica ha proporcionado algunos ejemplos del "precio de la abstracción". Los dos más destacados son para la eliminación y clasificación gaussianas. A saber: Se sabe que la eliminación gaussiana es óptima para, por ejemplo, calcular el determinante si restringe las operaciones a...
Después de la publicación Qué libros deberían leer todos , noté que hay libros recientes cuyos borradores están disponibles en línea. Por ejemplo, la entrada de Algoritmos de aproximación de la publicación anterior cita un libro de 2011 (aún por publicar) titulado El diseño de algoritmos de...
¿Cuál es el trabajo publicado más divertido relacionado con TCS que conoces? Por favor incluya solo aquellos que están destinados a ser divertidos. Se prefieren las obras que están explícitamente diseñadas para ser inteligentemente humorísticas (en lugar de, por ejemplo, una colección publicada de...
Enumere ejemplos en los que se utilizó por primera vez un teorema de las matemáticas que normalmente no se consideraba aplicable en informática para probar un resultado en informática. Los mejores ejemplos son aquellos en los que la conexión no era obvia, pero una vez que se descubrió, es...
En una respuesta a una pregunta anterior , mencioné la creencia común pero falsa de que la eliminación "gaussiana" se ejecuta en el tiempo O(n3)O(n3)O(n^3) . Si bien es obvio que el algoritmo utiliza operaciones aritméticas O(n3)O(n3)O(n^3) , la implementación descuidada puede crear números con...
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...
Estoy familiarizado con muchos resultados que usan el teorema de PCP (principalmente en algoritmos de aproximación), pero nunca he encontrado una explicación clara del teorema de PCP (es decir, que ).N P = P C P (O(log( n ) ) , O ( 1 ) )nortePAGS=PAGSCPAGS(O(Iniciar sesión(norte)),O(1))\mathsf{NP}...
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...
En TCS a menudo utilizamos resultados e ideas poderosas de las matemáticas clásicas (álgebra, topología, análisis, geometría, etc.). ¿Cuáles son algunos ejemplos de cuándo ha sido al revés? Aquí hay algunos que conozco (y también para dar una idea del tipo de resultados que estoy...
En Complejidad descriptiva , Immerman tiene Corolario 7.23. Las siguientes condiciones son equivalentes: 1. P = NP. 2. Sobre estructuras finitas, ordenadas, FO (LFP) = SO. Esto puede considerarse como "amplificación" de P = NP a un enunciado equivalente sobre (presumiblemente) clases de...
Para (versiones de búsqueda) de problemas completos de NP , verificar una solución es claramente más fácil que encontrarla, ya que la verificación se puede hacer en tiempo polinómico, mientras que encontrar un testigo lleva (probablemente) tiempo exponencial. En P , sin embargo, la solución...
El teorema de Ladner establece que si P ≠ NP, entonces hay una jerarquía infinita de clases de complejidad que contienen estrictamente P y estrictamente contenidas en NP. La prueba utiliza la integridad de SAT bajo reducciones de muchos en NP. La jerarquía contiene clases de complejidad construidas...
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...
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...
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...
Esta es una publicación cruzada de math.stackexchange. Deje que FACT denote el problema de factorización de enteros: dado encuentre los primos y los enteros modo quep i ∈ N , e i ∈ N , n = ∏ k i = 0 p e i i .n ∈ N ,n∈N,n \in \mathbb{N},pagsyo∈ N ,pi∈N,p_i \in \mathbb{N},miyo∈ N ,ei∈N,e_i \in...
Estoy buscando una respuesta definitiva sobre si la generación de números "verdaderamente aleatorios" es computable por Turing. No sé cómo expresar esto con precisión. Esta pregunta de StackExchange sobre "algoritmos eficientes para la generación de números aleatorios" se acerca a responder mi...