Recorridos casuales por pruebas

Hoy Ryan Williams publicó un artículo en arXiv (aparecido anteriormente en SIGACT News) que contiene una versión menos técnica de su reciente técnica ACC de límite inferior.

Mi pregunta no es sobre la técnica en sí misma (por supuesto digna de elogios inmensos), sino sobre el estilo del artículo. En resumen, escribe:

La prueba se describirá desde la perspectiva de alguien que intenta descubrirlo.

¡Increíble! En la sección de Fondo agrega:

Este artículo es una discusión sobre cómo descubrir la prueba: un recorrido informal a su alrededor. No se darán todos los detalles, pero verá de dónde provienen todas las piezas y cómo encajan. El camino estará lleno de mis propias intuiciones sesgadas sobre la teoría de la complejidad: lo que creo que debería y no debería ser cierto, y por qué. Gran parte de esta intuición puede estar equivocada; Sin embargo, puedo decir que me ha llevado en una dirección productiva al menos en una ocasión.

Esto es asombroso y es la primera vez que lo veo. Siempre me he preguntado por qué los autores de artículos no escriben cómo llegaron a la prueba, incluidos los enfoques fallidos que intentaron antes de llegar al camino que condujo a la solución. Cuando vi el artículo de Ryan sobre el arXiv, me sentí muy motivado para leerlo. Lo considero un documento revolucionario desde este punto de vista. La mayoría de las veces lo único que puede hacer con un documento es verificar su corrección.

La pregunta es la siguiente:

• ¿conoce otros documentos en TCS donde se presenta un resultado revolucionario en una "gira informal" en lugar de una serie de lemas técnicos?

Estoy hablando de publicaciones en revistas, no de publicaciones de blog o informes técnicos.

Además, lo etiqueté como una lista grande , con la esperanza de que realmente lo sea.

Hay un artículo (2001) de estilo similar de Lov Grover, que describe el camino hacia su innovador algoritmo de búsqueda cuántica (1996).

Tim Gowers es fanático de este tipo de cosas. Ver específicamente su exposición del método de aproximaciones de Razborov .

En su introducción, Gowers hace referencia a mi artículo expositivo sobre el forzamiento , que es un intento (no del todo exitoso) de hacer lo mismo para forzar. El forzamiento normalmente se considera una técnica en lógica y teoría de conjuntos, pero ocasionalmente se ha introducido en TCS. Aparece en el estudio de la aritmética limitada y la complejidad de la prueba proposicional (Krajíček y Takeuti son dos investigadores que han buscado esta conexión), y el concepto de un oráculo genérico está relacionado con el concepto de un filtro genérico.

(Esto comenzó como un comentario y se hizo demasiado largo).

Puede disfrutar el artículo de William Thurston sobre Prueba y Progreso en Matemáticas .

Las matemáticas en cierto sentido tienen un lenguaje común: un lenguaje de símbolos, definiciones técnicas, cálculos y lógica. Este lenguaje transmite eficientemente algunos, pero no todos, los modos de pensamiento matemático. Los matemáticos aprenden a traducir ciertas cosas casi inconscientemente de un modo mental a otro, de modo que algunas declaraciones se aclaran rápidamente. [...]

Las personas familiarizadas con las formas de hacer las cosas en un subcampo reconocen varios patrones de declaraciones o fórmulas como expresiones idiomáticas o circunlocución para ciertos conceptos o imágenes mentales. Pero para las personas que aún no están familiarizadas con lo que está sucediendo, los mismos patrones no son muy esclarecedores; a menudo son incluso engañosos. El lenguaje no está vivo excepto para quienes lo usan. [...]

Los matemáticos debemos esforzarnos mucho más en comunicar ideas matemáticas. Para lograr esto, debemos prestar mucha más atención a comunicar no solo nuestras definiciones, teoremas y pruebas, sino también nuestras formas de pensar. Necesitamos apreciar el valor de diferentes formas de pensar sobre la misma estructura matemática. Necesitamos enfocar mucha más energía en comprender y explicar la infraestructura mental básica de las matemáticas, con consecuentemente menos energía en los resultados más recientes. Esto implica desarrollar un lenguaje matemático que sea efectivo con el propósito radical de transmitir ideas a personas que aún no las conocen.

Con respecto a la pregunta original, hay documentos que no presentan ideas en el formato Definición-Teorema-Prueba (DTP). Timothy Chow tiene algunos documentos que se centran en comunicar ideas (aunque no son los primeros (o segundos) documentos sobre el tema / resultado).

1. Podrías haber inventado secuencias espectrales , Timothy Chow, Notices of the AMS
2. Forzando para tontos , Timothy Chow

Una posible razón para la prevalencia del formato DTP es que todos estamos acostumbrados a él a partir de libros y documentos. Los revisores (y lectores) a veces encuentran que el estilo de escritura no estándar distrae. Un término medio son los documentos que suavemente rompen al lector en un resultado. Hay documentos que presentan un caso especial o un problema simple que ilustra la idea general.

1. La estructura topológica de la computabilidad asincrónica , Maurice Herlihy y Nir Shavit. El documento tiene muchas ilustraciones y demuestra la idea general de un protocolo simple antes de aplicar el teorema principal para resolver algunos problemas abiertos.
2. $p$

Ninguna discusión sobre una presentación no estándar de ideas notables estaría completa sin mencionar el trabajo de Jean-Yves Girard . Único es probablemente la mejor palabra para describirlo (sin ser diplomático o sarcástico). De, el papel Lineal Logic .

La exégesis filosófica de las reglas de Heyting deja, de hecho, muy poco espacio para una discusión adicional sobre el cálculo intuicionista; pero alguien lo ha intentado seriamente? De hecho, la lógica lineal, que es una extensión clara y limpia de la lógica habitual, se puede alcanzar a través de un análisis más perspicaz de la semántica de las pruebas (no muy lejos del enfoque de la informática y, por lo tanto, relegado a la siguiente sección), o por ciertas consideraciones más o menos inmediatas sobre el cálculo posterior. Estas consideraciones tienen un significado geométrico inmediato, pero para comprenderlas, uno tiene que olvidar las intenciones, recordando, con un líder chino, que lo que importa no es el color del gato, sino el hecho de que atrapa ratones.

Más tarde:

Todavía hay personas que dicen que, para hacer informática, uno esencialmente necesita un soldador; Esta opinión es compartida por lógicos que desprecian la informática y por ingenieros que desprecian a los teóricos. Sin embargo, en los últimos años, la necesidad de un estudio lógico de la programación se ha vuelto cada vez más claro y el vínculo lógica-informática-ciencia parece irreversible. [...]
En cierto sentido, la lógica juega el mismo papel que el desempeñado por la geometría y la física: el marco geométrico impone ciertos resultados de conservación, por ejemplo, la fórmula de Stokes. Las simetrías de la lógica presumiblemente expresan una profunda conservación de la información, en una forma que aún no se ha conceptualizado correctamente.

Quizás los autores no incluyen estos intentos fallidos y la historia de la investigación en sus artículos publicados debido a las restricciones impuestas por los editores y los miembros de la PC. Supongo que es muy inusual que un diario (y probablemente aún más inusual para una conferencia) acepte un documento en el que la mayor parte está dedicado a intentos fallidos. Pero en la mayoría de los casos, si habla con los autores o expertos en el área, le explicarán la historia y los intentos fallidos (y muchos hablan de esto en los talleres).

He visto a varios autores explicar en arrendamiento de dónde provienen las ideas en sus documentos. Como ejemplo, Girard explica en su artículo que la idea de la lógica lineal surgió al tratar de encontrar una semántica denotacional para el OR intuicionista. Puede encontrar este tipo de información también en monografías y biografías de investigadores famosos y volúmenes dedicados a ellos (me vino a la mente la autobiografía de Halmos y más reciente "Kreiseliana: Sobre y alrededor de Georg Kreisel " editado por Odifreddi, también hay volúmenes y artículos dedicado a algunos teóricos de la complejidad). Esperemos que más personas hagan lo que Ryan ha hecho y sistemáticamente expliquen el proceso y cuenten la historia.

pd: puedes pensar en esto como una tradición oral de investigación :) (algo similar a la Torá Oral que no se permitió escribir ).

Hay un artículo publicado por Laszlo Babai (1990) en forma de una fábula sobre Arthur y Merlin que describe la secuencia dramática de eventos que llevaron a la comunidad al resultado IP = PSPACE en 1989, que fue increíble un año antes.