Como você obtém uma "Intuição Física" para obter resultados no TCS?

Sinto muito se esta pergunta é um pouco vaga, mas estou curioso para saber como os pesquisadores bem-sucedidos "sentem" os resultados no TCS.

Por exemplo, álgebra linear pode ser entendida geometricamente ou em termos de suas interpretações físicas (vetores próprios podem ser considerados "pontos estáveis" em um sistema) etc.) Também é intuitivo que exista um protocolo IP para TQBF (como o IP O protocolo pode ser visualizado como uma espécie de "jogo" entre duas entidades de poder computacional muito diferente). No entanto, acho que muitos dos resultados, mesmo os extremamente básicos no TCS, não têm intuições tão simples (MA AM). Pior ainda, ocasionalmente, intuições não refinadas ficam muito cautelosas (o 2-SAT está em P enquanto o 3-SAT não se acredita estar em P (na verdade, é NP-completo)). Existem "princípios gerais" para o desenvolvimento de uma intuição no TCS?$\subseteq$

Como muitos campos científicos, pode levar anos para construir a intuição, mas pode levar apenas uma nova idéia para derrubá-la (e, esperançosamente, algo agradável seja reconstruído em seu lugar).

Existem alguns exercícios básicos que você pode usar para tentar criar intuição para alguns papéis que você está lendo e parece que não consegue penetrar. Aqui está um que eu ainda faço de tempos em tempos. Comece com uma prova que você não entende, mas realmente gostaria, que é muito longa. Ao ler cada parágrafo da prova, tente escrever uma frase com suas próprias palavras sobre o que você acha que o parágrafo está dizendo, nas margens. Esperamos que a prova seja escrita suficientemente bem para que haja "partes" bem definidas na prova ("faça X, defina uma nova função f, depois aplique X a f, ..."). Caso contrário, a partir de suas frases, separe a prova em suas próprias partes.

$MA \subseteq AM$, Eu diria algo como "FAÇA ARTHUR FALAR MAIS". Mas talvez algo mais na prova pareça ser a idéia "chave" para você, o que é perfeitamente correto. É a sua intuição!)

Acho que minha sugestão pode ser útil para a maioria das matemáticas, mas achei muito útil para o TCS, onde muitas provas realmente se resumem a 1-2 idéias realmente novas, e o resto é uma síntese dessa idéia com o que já era conhecido.

Tenha cuidado com a intuição. Ele vem com muita experiência, pode estar errado e certo ao mesmo tempo e não é único. O ponto é que todos trazem sua própria intuição para os problemas com base em suas próprias zonas de conforto, nas necessidades do problema e em seus antecedentes. Como Tsuyoshi aponta, a intuição é realmente muito trabalho duro que foi sublimado em algumas imagens mentais concisas.

Portanto, minha sugestão seria: apenas trabalhe nos problemas que você gosta e tente desenvolver suas próprias idéias, mesmo se houver outro trabalho por aí. Você construirá a intuição dessa maneira. E se um resultado parece intrigante, isso significa que você ainda não o entendeu, ou talvez haja um resultado mais simples à espreita em algum lugar abaixo, esperando ser descoberto.

Como você conta os jogos como um exemplo de "intuição física", enquanto eu não consigo ver nada relacionado à física nos jogos, presumo que sua ênfase não esteja em "físico", mas em "intuição".

Argumento que parte do objetivo do estudo (educação ou pesquisa) em ciência da computação teórica é desenvolver a intuição para as noções abstratas relacionadas à computação. A intuição é adquirida estudando e familiarizando-se com o conceito. Não espero que exista um bom atalho.

Por exemplo, estudantes de graduação ficarão surpresos com a indecidibilidade de interromper o problema (provavelmente porque a mera existência de uma linguagem indecidível já é surpreendente). Mas aprender o fato, sua prova, alguns resultados relacionados e a ampla aplicabilidade da técnica de prova tornam esse resultado surpreendente menos surpreendente e de fato muito natural. Eu acredito que o mesmo é verdade para resultados mais complicados.

Quanto ao resultado específico, não concordo que não haja intuição simples para o MA⊆AM. (Aviso: atualmente estou estudando isso e os resultados relacionados, e posso dizer algo incorreto.) Em um sistema de MA, Merlin precisa dar uma resposta única que se encaixe na maioria das seqüências aleatórias usadas por Arthur. Mudamos o sistema para que Arthur envie várias seqüências aleatórias (polinomialmente muitas) a Merlin, e Merlin precisa dar uma resposta única que se encaixa em todas elas, o que me parece uma coisa natural de tentar. A comprovação da robustez deste sistema AM é uma aplicação simples do limite de Chernoff. Eu não acho que qualquer coisa nesse resultado seja conceitualmente difícil de entender.

Marginalmente relacionado: sua pergunta me lembrou uma linda postagem no blog “ Abstração, intuição e a 'falácia do tutorial de mônada' ” de Brent Yorgey, onde ele explicou a dificuldade de comunicar a intuição por uma não-explicação fictícia “Mônadas são burritos”. Se a explicação acima de como a prova do MA⊆AM funciona não faz sentido, eu posso estar demonstrando a mesma falácia. :(

Se você passa cinco anos de sua vida estudando um conceito puramente teórico X (por exemplo, um determinado modelo esotérico de computação), então eventualmente X se torna uma parte natural de sua vida diária.

Você aprenderá a saber como o X se comporta, como é, como responde às suas manipulações e em que tipo de bairro ele vive. Você aprenderá quem a descobriu, quando, por que e o que outras pessoas fizeram com o X, com ou sem êxito. Você conhecerá o X exatamente como qualquer objeto físico que encontrar todos os dias.

Na verdade, você pode conhecê-lo muito melhor do que aquelas coisas físicas estranhas, mal definidas, imprevisíveis e erráticas ... Mas é um longo caminho, e não acho que existam muitos atalhos mágicos.

As respostas aqui já cobrem a maioria das boas sugestões sobre intuição. Ainda assim, daria mais uma, que é útil no desenvolvimento de intuições durante a escrita em papel. Isto é sugerido pelo meu próprio professor, Hsueh-I Lu, que achei muito útil.

Sempre que um resultado for anotado e a correção parecer verificada, reescreva o artigo inteiro . Desta vez, temos que nos forçar a não usar palavras ou definições semelhantes às versões anteriores. Isso nos faz pensar de uma maneira completamente nova e diferente, e novas intuições se desenvolverão. Além disso, perturbe todos os parâmetros usados ​​no artigo, veja se algum conjunto de parâmetros difere do que usamos originalmente ainda funciona. Muitas vezes, alguns erros expostos ao reescrever o artigo. Crie novas idéias para superá-las.

Finalmente, após rodadas de reescrita, teremos uma boa intuição sobre o nosso próprio resultado, e não seremos muito otimistas / pessimistas com o poder das novas idéias apresentadas no artigo, pois somos tentados por algumas vezes, e é claro que o que está funcionando e o que não está.

O mesmo método funciona se você estiver lendo um novo artigo e deseja obter mais algumas intuições que não sejam as fornecidas pela leitura.

No meu próprio caso, a maioria dos conceitos de TCS sobre os quais sinto alguma intuição são sobre os quais me apoiei por meio de resultados práticos. Se eu me pego evoluindo e usando o mesmo modelo ou algoritmo com sucesso por anos, ele tende a me distrair cada vez mais, até que eu possa descobrir por que o algoritmo foi bem-sucedido. Isso é particularmente verdadeiro se estiver na hora de reescrever - quero saber qual é a essência da TCS, para que não perca a poeira mágica durante a refatoração. Descobrir tudo isso geralmente requer (para mim) um mergulho profundo em 1936, aproximadamente, e relacionar o que venho fazendo com esses conceitos básicos. Certa vez, um amigo me aconselhou a "pensar como uma máquina de torcer" quando eu estava em um desses mergulhos, e esse conselho ficou comigo.