Hermosos resultados en TCS

Recientemente, un amigo mío (trabajando en TCS) mencionó en una conversación que "quería ver / saber todo (o la mayor cantidad posible) de los hermosos resultados en TCS en su vida". Esto me hizo preguntarme sobre los hermosos resultados en esta área y, por lo tanto, la motivación para la siguiente pregunta:

¿Qué resultados (o ideas), en su opinión, son hermosos en la informática teórica? Sería genial si mencionaras la razón también. [También estaría bien incluso si las ideas se originan en las matemáticas, pero han despertado interés y encontrado usos en TCS]

Comenzaría con una respuesta como el argumento diagonal de Cantor porque es simple, elegante y, sin embargo, un resultado poderoso.

La indecidibilidad del problema de detención.

Hermoso por muchas razones. Es un resultado imposible. La prueba utiliza diagonalización. La declaración se aplica a una amplia gama de modelos de computación. Se puede formular de varias maneras, particularmente, utilizando lenguajes de programación estándar. Fue un resultado decisivo en la historia de la informática. Ampliar esta afirmación lleva al Teorema de Rice, los grados de Turing y muchos otros resultados geniales. Etc. Etc. Etc.

En mi opinión, la correspondencia Curry-Howard es uno de los resultados teóricos más bellos, y el que me llevó a investigar.

La idea de que dos sistemas, programas por un lado, y pruebas por otro lado, tienen exactamente la misma estructura, es casi de naturaleza filosófica: ¿existen algunos "patrones de razonamiento" generales?

La posibilidad de la criptografía de clave pública, por ejemplo, el esquema de intercambio de claves Diffie-Hellman.

Rompe la preconcepción muy fuerte que las personas deben conocer antes de intercambiar secretos en un canal inseguro.

Estaba y todavía estoy sorprendido por el algoritmo de Euclides. Para mí, es un testimonio del poder del pensamiento humano: que las personas podrían concebir un algoritmo tan temprano (alrededor del 300 aC si confío en mi memoria).

Avance rápido, hay literatura que aturde la mente sobre el tema. Creo que la lista de Scott Aaronson debería ser útil a este respecto, sin embargo, como el propio Aaronson dice que no está completa (y no es completamente teórica)

La técnica de Yao para usar el Teorema Minmax de von Neumann para probar los límites inferiores de los Algoritmos Aleatorios. Lo encuentro como algo fuera de este mundo.

Método probabilístico para demostrar la existencia de objetos que nos resulta difícil construir, incluido el Lema local de Lovasz. Estas técnicas son tan simples, pero tan poderosas.

Construcciones de la teoría de codificación de Madhu Sudán utilizando polinomios.

Expansores (esto comenzó como gráficos de Ramanujan) y Extractores y sus aplicaciones en Pseudoaleatoriedad.

Algoritmo de transformación rápida de Fourier de Cooley y Tukey para encontrar DFT. (Sin embargo, como asumió Tukey, ¡esto fue un redescubrimiento de una técnica bien conocida, al menos conocida por Gauss!)

El teorema de Barrington (un resultado muy sorprendente en su momento)

Teorema de repetición paralela (aunque el resultado es bueno, la prueba no es fácil)

Función Lovasz Theta para estimar la capacidad de shannon de un gráfico.

Algoritmo elipsoide que mostró que LP está en P, sorprendiendo a muchos en un momento en que muchos todavía sospechaban que podría ser NP-Completo.

Sorprendentemente, una de las respuestas más obvias no se ha agregado todavía. a veces uno trabaja demasiado con algo para verlo imparcialmente. La teoría de la integridad de NP lanzada por Cook / Levin e inmediatamente amplificada por Karp, quien dio una indicación temprana de su ubicuidad, aún más profética en retrospectiva. En muchos sentidos, este es el nacimiento de la teoría moderna de TCS y complejidad, y su pregunta central / clave / notoria P =? NP todavía está abierta después de cuatro décadas de intenso estudio / ataque. P =? NP tiene un premio Claymath de $ 1M por su solución.

La prueba Cook introdujo el NDTM, que aparentemente no es en absoluto una mera curiosidad teórica, sino una parte casi extremadamente fundamental de TCS. lanzó mil naves, por así decirlo. además, continuamente resiste / desafía los esfuerzos a través de una de las otras técnicas TCS clave / poderosas mencionadas en esta lista, la diagonalización, vista, por ejemplo, en los resultados de Oracle / Relativización BGS-75, lo que sugiere que debe haber algo exótico y diferente sobre cualquier posible solución, también sugerida / ampliada por el documento Razborov-Rudich Natural Proofs (premio Godel 2007).

Hay muchas, muchas referencias en el subj pero una más reciente con algún relato de primera mano de la historia se puede encontrar en The P =? NP Question y Godel's Lost Letter por RJ Lipton

La complejidad de Kolmogorov y el método de incompresibilidad .

El método de incompresibilidad, basado en la complejidad de Kolmogorov, proporcionó una forma nueva e intuitiva de formular pruebas. En una prueba típica que usa el método de incompresibilidad, primero se elige un objeto incompresible de la clase en discusión. El argumento invariablemente dice que si una propiedad deseada no se cumple, entonces, en contraste con la suposición, el objeto puede comprimirse y esto genera la contradicción requerida.

Vea, por ejemplo, la prueba de que hay un número infinito de números primos, la prueba alternativa del teorema de incompletitud de Godel o las conexiones entre la complejidad de Kolmogorov y la complejidad computacional ...

Estaba (y todavía estoy) asombrado por el segundo teorema de recursión de Kleene . En la superficie, parece simple y no muy útil, pero luego descubrí que es profundo tanto matemática como filosóficamente.

Cuando también leí acerca de la variante probada en Turing Machines (muy informalmente afirmando que las máquinas pueden obtener sus propias descripciones o, de manera equivalente, que hay máquinas que generan su propia descripción, como un programa que se imprime ...), sentí que mi cerebro se retorcía tan duro, pero intrigado como nunca antes. Luego, verá cómo se utiliza el teorema para proporcionar pruebas de una línea para la indecidibilidad del problema de detención y la irreconocibilidad de máquinas mínimas ... etc.

Fuente y teoremas de codificación de canales de Shannon.

Una definición matemática que distinguía entre el transmisor, el receptor y el medio y que ignoraba la semántica del mensaje fue un gran paso. La entropía, en el contexto de los datos, es una noción fantásticamente útil. Y porque la teoría de la información debería ser mejor conocida.

Un hermoso resultado que se basa en el teorema de PCP establece que es computacionalmente difícil (NP-difícil) satisfacer más de 7/8 de las cláusulas de la fórmula 3SAT incluso para las que son satisfactorias.

algoritmo shors para factorizar en BQP . en mi opinión / memoria, la computación cuántica fue más que una curiosidad teórica hasta este resultado en 1994, momento en el que parece que la literatura y el interés de la investigación en computación QM explotaron. sigue siendo posiblemente uno de los algoritmos QM más importantes conocidos. galardonado con el premio Gödel 1999. también revela que la factorización en la computación QM en realidad se comprende mejor en cierto sentido que en la computación clásica, donde, por ejemplo, la cuestión de si la factorización es NP completa aún está abierta.

Me parece que la prueba de primalidad AKS P-time es bastante hermosa en varios sentidos. un avance en el momento, uno de los grandes pero raros avances vistos en la teoría de la complejidad en nuestras vidas. resuelve un problema que se remonta a la antigüedad griega y se relaciona con algunos de los primeros algoritmos inventados (tamiz de eratóstenes), es decir, identificar primos de manera eficiente. es una prueba constructiva de que la detección de primalidades está en P en oposición a muchas pruebas excelentes que desafortunadamente no son constructivas.

está interconectado con el algoritmo de criptografía RSA mencionado en otra respuesta porque ese algoritmo necesita encontrar primos grandes rápidamente, antes del algoritmo AKS esto solo era probabilísticamente posible. está fundamentalmente relacionado con la teoría de números y otros problemas profundos, por ejemplo, la conjetura de Riemann que, en muchos sentidos, es el ámbito original de la algorítmica.

galardonado con el Premio Gödel 2006 y el Premio Fulkerson 2006

Creo que el teorema de gráficos menores de Robertson y Seymour fue la teoría más maravillosa que he visto (y la leí parcialmente). En primer lugar, es bastante complicado, pero las conjeturas básicas no son difíciles y es posible que todos los que trabajan en TCS puedan adivinarlas. Su esfuerzo extremo para demostrarlos fue maravilloso. De hecho, después de leer algunos de los artículos de esa serie, entiendo el poder de la mente humana.

Además, el teorema menor del gráfico tiene un gran impacto en diferentes campos de TCS. Como teoría de grafos, algoritmo de aproximación, algoritmos parametrizados, lógica, ...

Uno de mis resultados favoritos es que varios problemas de naturaleza aparentemente infinita son decidibles.

1. La teoría del primer orden de los campos cerrados reales es decidible (por Tarski). La geometría euclidiana también es un modelo de los axiomas de los campos realmente cerrados, por lo tanto, según Tarski, las declaraciones de primer orden en este modelo son decidibles.
2. La aritmética previa a la hamburguesa es decidible.
3. La teoría de primer orden de los campos cerrados algebraicamente (esto incluye números complejos) es decidible.
4. La lógica monádica de segundo orden sobre palabras infinitas (y finitas) es decidible. La prueba es elegante y se puede enseñar a estudiantes de pregrado.

Hay muchos resultados encantadores sobre los algoritmos probabilísticos, que son engañosamente simples y un gran paso adelante en la forma en que pensamos sobre la computación.

El truco de von Neumann para implementar una moneda justa con una sesgada. Estamos tan acostumbrados a los algoritmos probabilísticos ahora, pero desde una perspectiva externa, esto es increíblemente genial. Tanto el algoritmo como la prueba son accesibles para cualquiera que conozca la probabilidad de la escuela secundaria.

El resultado de Tim Griffin es que los operadores de control call/ccestán relacionados con la lógica clásica, extendiendo la correspondencia Curry-Howard.

call/cc$E$$\neg\neg \tau$$\mathtt{call/cc}{(E)}$$\tau$$\neg\tau$$\tau\rightarrow\bot$$\tau$

Su artículo , "Una noción de control de Fórmulas como tipos", aparece en POPL 1990.

Mi favorito es el algoritmo de tiempo lineal de Rabin para calcular el par de puntos más cercano en el plano (o más precisamente su simplificación). Transmite la importancia del modelo de computación, el poder de los algoritmos aleatorios y alguna forma elegante de pensar en algoritmos aleatorios.

Dicho esto, CS todavía está lejos de alcanzar el nivel de elegancia que uno encuentra en matemáticas (bueno, tenían 5000 años de ventaja), desde definiciones básicas / resultados en cálculo, topología (teoremas de punto fijo), combinatoria, geometría (teorema de Pitágoras http : //en.wikipedia.org/wiki/File: Pythag_anim.gif ), etc.

Si buscas belleza, búscala en todas partes ...

Este resultado es probablemente un poco reciente para calificar como fundamental, pero creo que la interpretación de tipos como homotopía califica. Esta vista permite interpretar tipos de teoría constructivos como conjuntos con ciertas propiedades geométricas, en este caso, la homotopía .

Considero que este punto de vista es particularmente hermoso, ya que hace que ciertas observaciones previamente complejas sobre la teoría de tipos sean simples, por ejemplo, el hecho de que el "axioma K" no es derivable .

Una descripción general de este campo en ciernes por Steve Awodey puede encontrarse aquí .

La prueba de conocimiento cero es un concepto muy interesante. Permite que una entidad, el probador, demuestre (con alta probabilidad) a otra entidad, el verificador, que conoce "un secreto" (una solución a algún problema NP, una raíz cuadrada modular de algún número, un discreto registro de algún número, etc. ...) sin dar ninguna información sobre el secreto (lo cual es difícil a primera vista, ya que la primera idea para demostrar que usted sabe un secreto es decir el secreto, y que cualquier comunicación que pueda resultar en el verificador cree que usted conoce el secreto a priori solo puede aumentar el conocimiento del verificador sobre el secreto).