Belos resultados no TCS

Recentemente, um amigo meu (trabalhando no TCS) mencionou em uma conversa que "ele queria ver / conhecer todos (ou tanto quanto possível) os belos resultados do TCS em sua vida". Isso meio que me fez pensar sobre os belos resultados nessa área e, portanto, a motivação para a seguinte pergunta:

Quais resultados (ou idéias), na sua opinião, são bonitos na ciência da computação teórica? Seria ótimo se você mencionasse o motivo também. [Também seria bom, mesmo que as idéias sejam originárias da matemática, mas tenham despertado interesse e encontrado usos no TCS]

Eu começaria com uma resposta como argumento diagonal de Cantor, porque é simples, elegante e, no entanto, um resultado poderoso.

A indecidibilidade do problema da parada.

Bonito por muitas razões. É um resultado impossível. A prova usa diagonalização. A declaração se aplica a uma ampla gama de modelos de computação. Ele pode ser formulado de várias maneiras, principalmente usando linguagens de programação padrão. Foi um resultado decisivo na história da computação. Estender esta declaração leva ao Teorema de Rice, aos graus de Turing e a muitos outros resultados interessantes. Etc. Etc. Etc.

Na minha opinião, a correspondência de Curry-Howard é um dos mais belos resultados teóricos e o que me levou a fazer pesquisas.

A idéia de que dois sistemas, programas, por um lado, e provas, por outro, têm exatamente a mesma estrutura, é quase de natureza filosófica: existem alguns "padrões de raciocínio" gerais?

A possibilidade de criptografia de chave pública, por exemplo, esquema de troca de chaves Diffie-Hellman.

Ele quebra o preconceito muito forte que as pessoas precisam conhecer antes de trocar segredos em um canal inseguro.

Fiquei e ainda estou surpreso com o algoritmo de Euclides. Para mim, é uma prova do poder do pensamento humano - que as pessoas possam conceber esse algoritmo tão cedo (por volta de 300 aC, se eu confiar na minha memória).

Avanço rápido, há literatura entorpecente sobre o assunto. Eu acho que a lista de Scott Aaronson deve ser útil nesse sentido - embora, como o próprio Aaronson diz que não é completo (e não é totalmente teórico)

A técnica de Yao para usar o Teorema Minmax de von Neumann para provar limites mais baixos para algoritmos randomizados. Eu acho isso como algo fora deste mundo.

Método probabilístico para provar a existência de objetos que achamos difíceis de construir, incluindo o lema local de Lovasz. Essas técnicas são tão simples, mas tão poderosas.

Construções da teoria de codificação de Madhu Sudão usando polinômios.

Expansores (que começaram como gráficos Ramanujan) e Extratores e suas aplicações no Pseudoaleatório.

O algoritmo Fast Fourier Transform de Cooley e Tukey para encontrar DFT. (Embora, como assumido por Tukey, tenha sido uma redescoberta de uma técnica bem conhecida, pelo menos conhecida por Gauss!)

Teorema de Barrington, (um resultado muito surpreendente em seu tempo)

Teorema da repetição paralela (embora o resultado seja bom, a prova não é fácil)

Função Lovasz Theta para estimar a capacidade de Shannon de um gráfico.

Algoritmo elipsóide que mostrou que o LP está em P, surpreendendo muitos no momento em que muitos ainda suspeitavam que poderia ser NP-Complete.

surpreendentemente, uma das respostas mais óbvias ainda não foi adicionada. às vezes se trabalha demais com algo para vê-lo imparcialmente. a teoria da completude da PN lançada por Cook / Levin e imediatamente amplificada por Karp, que deu uma indicação precoce de sua onipresença, ainda mais presciente em retrospecto. sob muitos aspectos, este é o nascimento da moderna teoria da complexidade e da TCS e sua questão central / chave / notória P =? NP ainda está aberta após quatro décadas de intenso estudo / ataque. P =? NP tem um prêmio Claymath de US $ 1 milhão por sua solução.

a prova de Cook introduziu o NDTM, que aparentemente não é uma mera curiosidade teórica, mas uma parte quase extremamente fundamental do TCS. lançou mil navios, por assim dizer. além disso, ele resiste / desafia continuamente os esforços por meio de uma das outras técnicas importantes / poderosas do TCS mencionadas nesta lista: diagonalização, vista, por exemplo, nos resultados do Oracle / Relativization do BGS-75 - sugerindo que deve haver algo exótico e diferente sobre qualquer possível solução, também sugerida / ampliada pelo documento Razborov-Rudich Natural Proofs (prêmio Godel de 2007).

existem muitos, muitos árbitros sobre o assunto, mas um mais recente com alguns relatos de primeira mão da história pode ser encontrado em The P =? NP Question e Godel's Lost Letter por RJ Lipton

Complexidade de Kolmogorov e o método da incompressibilidade .

O método de incompressibilidade - baseado na complexidade de Kolmogorov - forneceu uma maneira nova e intuitiva de formular provas. Em uma prova típica usando o método de incompressibilidade, primeiro se escolhe um objeto incompressível da classe em discussão. O argumento invariavelmente diz que, se uma propriedade desejada não se mantém, então, em contraste com a suposição, o objeto pode ser compactado e isso gera a contradição necessária.

Veja, por exemplo, a prova de que existe um número infinito de números primos, a prova alternativa do teorema da incompletude de Godel ou as conexões entre a Complexidade de Kolmogorov e a Complexidade Computacional .

Fiquei (e ainda estou) surpreso com o Segundo Teorema da Recursão de Kleene . Aparentemente, parece simples e pouco útil, mas depois descobri que é profundo, matematicamente e filosoficamente.

Quando também li sobre a variante comprovada nas Máquinas de Turing (afirmando muito informalmente que as máquinas podem obter suas próprias descrições ou equivalentemente que existem máquinas que produzem sua própria descrição, como um programa que se imprime ..), senti meu cérebro revirar. tão difícil, mas intrigado como nunca antes. Então, você vê como o teorema é usado para fornecer provas de uma linha para indecidibilidade de problemas de interrupção e irreconhecibilidade de máquinas mínimas ... etc.

Teoremas de codificação de fonte e canal de Shannon.

Uma definição matemática que distinguia entre transmitido, receptor e meio e que ignorava a semântica da mensagem era um grande passo. Entropia, no contexto de dados, é uma noção fantasticamente útil. E porque a teoria da informação deve ser mais conhecida.

Um belo resultado que se baseia no teorema do PCP afirma que é computacionalmente difícil (NP-hard) satisfazer mais de 7/8 das cláusulas da fórmula 3SAT, mesmo para as satisfatórias.

algoritmo shors para fatoração no BQP . na minha opinião / memória, a computação quântica era mais uma curiosidade teórica até esse resultado em 1994, quando parece que o interesse da literatura e da pesquisa em computação QM explodiu. ainda é indiscutivelmente um dos algoritmos QM mais importantes conhecidos. concedeu o prêmio Gödel de 1999. também revela que o fatoramento na computação QM é, de certo modo, um pouco melhor compreendido do que na computação clássica, onde, por exemplo, a questão de se o fatoramento é NP completo ainda está em aberto.

Parece-me que o teste de primalidade do tempo P da AKS é bastante bonito em vários sentidos. um avanço na época, um dos grandes, mas bastante raros, vistos na teoria da complexidade em nossas vidas. ele resolve um problema que remonta à antiguidade grega e se relaciona com alguns dos primeiros algoritmos inventados (peneira de eratóstenes), ou seja, identificar os primos com eficiência. é uma prova construtiva de que a detecção de primalidade está em P, em oposição a muitas grandes provas que infelizmente não são construtivas.

está interconectado ao algoritmo de criptografia RSA mencionado em outra resposta, porque esse algoritmo precisa encontrar números primos grandes rapidamente, antes do algoritmo AKS, isso era apenas probabilisticamente possível. está fundamentalmente ligado à teoria dos números e outros problemas profundos, por exemplo, a conjectura de Riemann que, de muitas maneiras, é o domínio original da algorítmica.

concedeu o Prêmio Gödel de 2006 e o ​​Prêmio Fulkerson de 2006

Acho gráfico teorema menor de Robertson e Seymour foram as teorias mais maravilhosas que já vi (e o li parcialmente). Antes de tudo, é bastante complicado, mas as conjecturas básicas não são difíceis e pode ser que todos que trabalham no TCS possam adivinhar. O esforço extremo deles para prová-los foi maravilhoso. De fato, depois de ler alguns dos documentos dessa série, entendo o poder da mente humana.

Também o teorema menor do gráfico tem um grande impacto em diferentes campos do TCS. Como teoria dos grafos, algoritmo de aproximação, algoritmos parametrizados, lógica, ...

Uma das minhas famílias favoritas de resultados é que vários problemas de natureza aparentemente infinita são decidíveis.

1. A teoria de primeira ordem dos campos fechados reais é decidível (por Tarski). A geometria euclidiana também é um modelo dos axiomas dos campos reais reais, portanto, por Tarski, as instruções de primeira ordem nesse modelo são decidíveis.
2. A aritmética do pré -burger é decidível.
3. A teoria de primeira ordem de campos algebricamente fechados (isso inclui números complexos) é decidível.
4. A lógica monádica de segunda ordem sobre palavras infinitas (e finitas) é decidível. A prova é elegante e pode ser ensinada a estudantes de graduação.

Existem muitos resultados encantadores sobre algoritmos probabilísticos, que são enganosamente simples e um grande passo à frente na maneira como pensamos sobre computação.

truque de von Neumann para implementar uma moeda justa com uma moeda tendenciosa. Estamos tão acostumados com algoritmos probabilísticos agora, mas de uma perspectiva externa, isso é incrivelmente legal. Tanto o algoritmo quanto a prova são acessíveis a quem conhece a probabilidade do ensino médio.

O resultado de Tim Griffin, que controla operadores como call/ccos relacionados à lógica clássica, ampliando a correspondência de Curry-Howard.

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

Seu artigo , "Uma noção de controle de fórmulas como tipos", aparece no POPL 1990.

O meu favorito é o algoritmo de tempo linear de Rabin para calcular o par de pontos mais próximo no plano (ou mais precisamente sua simplificação). Ele mostra a importância do modelo de computação, o poder dos algoritmos aleatórios e uma maneira elegante de pensar sobre algoritmos aleatórios.

Dito isto, o CS ainda está longe de alcançar o nível de elegância que se encontra em matemática (bem, eles tiveram 5000 anos de vantagem), de definições / resultados básicos em cálculo, topologia (teoremas de pontos fixos), combinatória, geometria (teorema de Pitágoras http : //en.wikipedia.org/wiki/File: Pythag_anim.gif ), etc.

Se você procura beleza, procure em qualquer lugar ...

Esse resultado provavelmente é um pouco recente para ser qualificado como fundamental, mas acredito que a interpretação de tipos como homotopia se qualifica. Esta visão permite interpretar tipos da teoria construtiva de tipos como conjuntos com certas propriedades geométricas, neste caso homotopia .

Acho esse ponto de vista particularmente bonito, pois simplifica certas observações anteriormente complexas sobre a teoria dos tipos, por exemplo, o fato de que o "axioma K" não é derivável .

Uma visão geral desse campo de Steve Awodey pode ser encontrada aqui .

A prova de zero conhecimento é um conceito muito interessante. Ele permite que uma entidade, o provador, prove (com alta probabilidade) a outra entidade, o verificador, que conhece "um segredo" (uma solução para algum problema de NP, uma raiz quadrada modular de algum número, uma discreta registro de algum número, etc.) sem fornecer nenhuma informação sobre o segredo (o que é difícil à primeira vista, pois a primeira idéia para provar que você conhece um segredo é realmente contar o segredo e que qualquer comunicação que possa resultar em o verificador acreditando que você conhece o segredo pode, a priori, apenas aumentar o conhecimento do verificador sobre o segredo).