¿Cómo se obtiene una "intuición física" para obtener resultados en TCS?

Lamento si esta pregunta es un poco vaga, pero tengo curiosidad por saber cómo los investigadores exitosos tienen una "idea" de los resultados en TCS.

Por ejemplo, el álgebra lineal puede entenderse geométricamente o en términos de sus interpretaciones físicas (los vectores propios pueden considerarse "puntos estables" en un sistema), etc. También es intuitivo que existe un protocolo IP para TQBF (como IP El protocolo puede ser visualizado como una especie de "juego" entre dos entidades de potencia computacional muy diferente). Sin embargo, encuentro que muchos de los resultados, incluso los extremadamente básicos en TCS no tienen intuiciones tan simples (MA AM). Peor aún, ocasionalmente, las intuiciones sin refinar se vuelven extremadamente cautelosas (2-SAT está en P mientras que 3-SAT no se cree que esté en P (de hecho, es NP-completo)). ¿Hay algún "principio general" para desarrollar una intuición en TCS?$\subseteq$

Al igual que muchos campos científicos, puede llevar años desarrollar la intuición, pero solo puede tomar una nueva idea para derribar esa intuición (y es de esperar que algo bueno se reconstruya en su lugar).

Hay algunos ejercicios básicos que puedes usar para tratar de desarrollar la intuición de un artículo que estás leyendo y parece que no puedes penetrar. Aquí hay uno que todavía hago de vez en cuando. Comienza con una prueba que no entiendas pero que realmente te gustaría, que es muy larga. Mientras lee cada párrafo de la prueba, intente escribir una oración con sus propias palabras sobre lo que cree que dice el párrafo, en los márgenes. Esperemos que la prueba se escriba lo suficientemente bien como para que haya "partes" bien definidas para la prueba ("hacer X, luego definir una nueva función f, luego aplicar X a f, ..."). De lo contrario, separe la prueba en sus propias partes de sus oraciones.

Ahora, para cada parte, intente escribir una oración (en sus propias palabras) sobre lo que está haciendo cada parte. En este punto, podría ser que encuentre que sus oraciones anteriores no son del todo precisas o no encajan bien (su intuición estaba "apagada"), por lo que puede refinarlas para que encajen lógicamente. Ahora tiene algunas oraciones que resumen toda la prueba. Luego (ahora esta última parte es de mi asesor, Manuel Blum) trate de pensar en una palabra o frase para todo el asunto. Esta frase sería la idea clave que, en su opinión, es lo que hace que todo el argumento comience. (Por ejemplo, la mayoría de las pruebas de existencia a través del método probabilístico se pueden resumir en: "PICK RANDOM". En el caso de$MA \subseteq AM$, Yo diría algo como "HAZ QUE ARTHUR HABLE MÁS". Pero tal vez algo más en la prueba parece ser la idea "clave" para usted, lo cual está perfectamente bien. ¡Es tu intuición!)

Supongo que mi sugerencia puede ser útil para la mayoría de las matemáticas, pero la encontré muy útil para TCS, donde muchas pruebas realmente se reducen a 1-2 ideas realmente nuevas, y el resto es una síntesis de esa idea con lo que ya se sabía.

Ten cuidado con la intuición. Viene con una gran experiencia, a menudo puede ser incorrecto y correcto al mismo tiempo, y no es único. El punto es que todos aportan su propia intuición a los problemas en función de sus propias zonas de confort, las necesidades del problema y sus antecedentes. Como Tsuyoshi señala, la intuición es realmente mucho trabajo duro que se ha sublimado en unas pocas imágenes mentales concisas.

Por lo tanto, mi sugerencia sería: solo trabaje en los problemas que le gustan y trate de desarrollar sus propias ideas, incluso si hay otro trabajo por ahí. Desarrollarás la intuición de esa manera. Y si un resultado parece desconcertante, significa que aún no lo ha entendido del todo, o tal vez hay un resultado más simple que acecha en algún lugar debajo, esperando ser descubierto.

Como usted considera los juegos como un ejemplo de "intuición física" mientras no puedo ver nada relacionado con la física en los juegos, asumo que su énfasis no está en "física" sino en "intuición".

Sostengo que parte del propósito del estudio (educación o investigación) en informática teórica es desarrollar la intuición para las nociones abstractas relacionadas con la computación. La intuición se adquiere al estudiar y familiarizarse con el concepto. No espero que haya un buen atajo.

Por ejemplo, los estudiantes universitarios se sorprenderán por la indecidibilidad del problema de detención (probablemente porque la mera existencia de un idioma indecidible ya es sorprendente). Pero conocer el hecho, su prueba, algunos resultados relacionados y la amplia aplicabilidad de la técnica de prueba hace que este sorprendente resultado sea menos sorprendente y, de hecho, muy natural. Creo que lo mismo es cierto para resultados más complicados.

En cuanto al resultado específico, no estoy de acuerdo en que no haya una intuición simple para MA⊆AM. (Advertencia: actualmente estoy estudiando esto y los resultados relacionados, y puedo decir algo incorrecto). En un sistema de MA, Merlin tiene que dar una respuesta única que se ajuste a la mayoría de las secuencias aleatorias utilizadas por Arthur. Cambiamos el sistema para que Arthur envíe varias secuencias aleatorias (polinomialmente muchas) a Merlín y Merlín tiene que dar una respuesta única que se ajuste a todas ellas, lo que me parece algo natural de probar. Probar la solidez de este sistema AM es una aplicación simple del límite de Chernoff. No creo que nada en este resultado sea conceptualmente difícil de entender.

Relacionado marginalmente: su pregunta me recordó una hermosa publicación de blog “ Abstracción, intuición y la 'falacia del tutorial de mónada' ” por Brent Yorgey, donde explicó la dificultad de comunicar la intuición mediante una no ficción ficticia “Las mónadas son burritos”. Si la explicación anterior de cómo funciona la prueba de MA⊆AM no tiene ningún sentido, podría estar demostrando la misma falacia. :(

Si pasas cinco años de tu vida estudiando un concepto puramente teórico X (p. Ej., Cierto modelo esotérico de cómputo), finalmente X se convierte en una parte natural de tu vida diaria.

Aprenderá a saber cómo se comporta X, cómo se siente, cómo responde a sus manipulaciones y en qué tipo de vecindario vive. Aprenderá quién lo descubrió, cuándo y por qué, y qué han hecho otros con X, con éxito o sin éxito. Conocerás X al igual que cualquier objeto físico que encuentres todos los días.

De hecho, puede saberlo mucho mejor que esas cosas físicas extrañas, mal definidas, impredecibles y erráticas ... Pero es un largo camino, y no creo que haya tantos atajos mágicos.

Las respuestas aquí ya cubren la mayoría de las buenas sugerencias sobre la intuición. Aún así, le daría uno más, lo cual es útil cuando se desarrollan intuiciones durante la redacción del artículo. Esto es sugerido por mi propio maestro, Hsueh-I Lu, que me pareció muy útil.

Siempre que se escriba un resultado, y la corrección parezca verificada, reescriba todo el artículo . Esta vez tenemos que obligarnos a no usar palabras o definiciones similares a las versiones anteriores. Esto nos hace pensar de una manera completamente nueva y diferente, y se desarrollarán nuevas intuiciones. Además, perturbe todos los parámetros utilizados en el documento, vea si algún conjunto de parámetros difiere del que usamos originalmente todavía funciona. A menudo se exponen algunos errores al reescribir el artículo. Proponga nuevas ideas para superarlas.

Finalmente, después de rondas de reescritura, tendremos una intuición agradable y redonda sobre nuestro propio resultado, y no seremos demasiado optimistas / pesimistas con respecto al poder de las nuevas ideas presentadas en el documento, ya que estamos probando por un par de veces, y está claro que lo que funciona y lo que no.

El mismo método funciona si está leyendo un nuevo artículo y desea obtener más intuiciones que la que le da la lectura.

En mi propio caso, la mayoría de los conceptos de TCS de los que creo que tengo alguna intuición son aquellos a los que apoyé a través de resultados prácticos. Si me encuentro evolucionando y usando el mismo modelo o algoritmo con éxito durante años, tiende a llevarme cada vez más a la distracción hasta que puedo descubrir por qué el algoritmo ha tenido éxito. Esto es particularmente cierto si es hora de una reescritura: quiero saber cuál es la esencia TCS de la cosa, para que no pierda el polvo mágico mientras refactorizo. Entender todo eso generalmente requiere (para mí) una inmersión profunda de vuelta a 1936 más o menos, y relacionar lo que he estado haciendo con esos conceptos básicos. Una vez, un amigo me aconsejó "pensar como una máquina de turing" cuando estaba en una de esas inmersiones, y ese consejo me ha quedado grabado.