Resultados de física no TCS?

Parece claro que vários subcampos da ciência da computação teórica foram significativamente afetados pelos resultados da física teórica. Dois exemplos disso são

1. Computação quântica
2. Resultados de mecânica estatística utilizados em análise de complexidade / algoritmos heurísticos.

Então, minha pergunta é: faltam áreas importantes?

Minha motivação é muito simples: sou um físico teórico que chegou ao TCS por meio de informações quânticas e estou curioso quanto a outras áreas em que as duas áreas se sobrepõem.

Essa é uma pergunta relativamente suave, mas não pretendo que seja uma pergunta do tipo lista grande. Estou procurando áreas onde a sobreposição é significativa.

A técnica de busca de recozimento simulado é inspirada no processo físico de recozimento em metalurgia.

O recozimento é um tratamento térmico em que a força e a dureza da substância a ser tratada podem mudar drasticamente. Muitas vezes, isso envolve o aquecimento da substância a uma temperatura extrema e, em seguida, permite que ela esfrie lentamente.

O recozimento simulado evita mínimos / máximos locais nos espaços de pesquisa, incorporando um grau de aleatoriedade (a temperatura) no processo de busca. À medida que o processo de busca prossegue, a temperatura esfria gradualmente, o que significa que a quantidade de aleatoriedade na busca diminui. Aparentemente, é uma técnica de pesquisa bastante eficaz.

No sentido inverso (do TCS à física), os estados dos produtos da matriz, PEPS (estados de pares emaranhados projetados), MERA (renomalização de entrelaçamento em múltiplas escalas ansatz) foram significativamente informados pelas idéias do TCS que foram adaptadas na teoria da informação quântica. Essas siglas são todas técnicas para aproximar os estados dos sistemas de spin quântico usados ​​pelos teóricos da matéria condensada e, em muitos casos, essas técnicas parecem funcionar melhor do que quaisquer ferramentas conhecidas anteriormente.

Sistemas complexos é um campo que tem muito a ver com análise de redes sociais e redes em geral, e foi invadido por físicos em grande número, manejando armas a partir de estatísticas e termodinâmica. Se foi invadido pela física é uma história diferente.

Um resultado de Pour-El e Richards Adv. Matemática. 39 215 (1981) fornece a existência de soluções não computáveis ​​para a equação da onda 3D para condições iniciais computáveis ​​usando a onda para simular uma máquina de Turing universal.

A conexão também é inversa. Há algum tempo, cientistas da computação teóricos que trabalham na teoria dos domínios se interessaram pela relatividade. Eles provaram resultados sobre como reconstruir a estrutura do espaço-tempo a partir da estrutura de causalidade. Isso é algo bastante familiar para os teóricos do domínio, onde os objetos de interesse básicos são ordens parciais cuja topologia é determinada pela ordem. Você pode dar uma olhada em http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf

Um exemplo muito antigo (que poderia ser incluído na resposta de Suresh, no entanto, essa é uma abordagem diferente) é a influência da teoria das redes elétricas, por exemplo, as leis de circuito de Kirchhoff, na combinatória, na teoria dos grafos e na probabilidade.

Uma área que viu algumas aplicações, mas não o suficiente para IMO, é aproximar estruturas ou processos distintos com aproximações analíticas. Esse é um grande negócio em matemática (por exemplo, teoria dos números analíticos) e física (toda a mecânica estatística), mas não se mostrou tão popular no CS por algum motivo.

Uma aplicação famosa disso foi no design da Connection Machine. Essa era uma máquina massivamente paralela e, como parte de seu design, eles precisam descobrir o tamanho do tamanho dos buffers no roteador. Feynman modelou o roteador com PDEs e mostrou que os buffers poderiam ser menores do que os argumentos indutivos tradicionais podiam estabelecer. Danny Hillis relata a história deste ensaio .

Teoria dos Gauges para aproximações heurísticas da programação inteira (alguns trabalhos de Misha Chertkov ). Métodos de grupo de renormalização para contagem combinatória, Cap.10-12 de "Elements of the Random Walk" de Rudnick / Gaspari. Aplicando a decomposição integral do caminho de Feymann (ie, Seção 9.5.1) à contagem de caminhadas que evitam a auto-evitação. Para conexão com o TCS, observe que o regime de tratabilidade para contagem aproximada de gráficos depende da taxa de crescimento de caminhadas que evitam a auto-evitação.

A física estatística deu aos cientistas da computação uma nova maneira de ver o SAT, como apresentado aqui . A idéia é que, à medida que a proporção de cláusulas para variáveis ​​envolvidas em uma fórmula 3-SAT aumenta de cerca de 4 para cerca de 5, deixamos de ser capazes de resolver a grande maioria das instâncias de 3-SAT e conseguimos resolver muito poucas. Essa transição é considerada uma "mudança de fase" no SAT.

Essa idéia ganhou notoriedade particular no verão passado com o suposto artigo de P vs. NP de Deolalikar.

A teoria dos sistemas distribuídos no início, especialmente os trabalhos de Leslie Lamport et al., Teve algum impacto da Relatividade Especial para obter a imagem correta e concordar (tolerante a falhas) em um estado global do sistema. Veja a entrada 27. ( Hora, Relógios e Ordenação de Eventos em um Sistema Distribuído , Comunicações da ACM 21, 7 (julho de 1978), 558-565) nos Escritos de Leslie Lamport , onde Lamport fornece as seguintes informações básicas sobre sua papel:

A origem deste artigo foi uma nota intitulada The Maintenance of Duplicate Databases por Paul Johnson e Bob Thomas. Acredito que a nota introduziu a idéia de usar registros de data e hora da mensagem em um algoritmo distribuído. Por acaso, tenho um entendimento sólido e visceral da relatividade especial (ver [5]). Isso me permitiu captar imediatamente a essência do que eles estavam tentando fazer. A relatividade especial nos ensina que não há uma ordenação total invariável de eventos no espaço-tempo; observadores diferentes podem discordar sobre qual dos dois eventos ocorreu primeiro. Existe apenas uma ordem parcial na qual um evento e1 precede um evento e2 se e1 puder afetar causalmente e2. Percebi que a essência de Johnson e Thomas O algoritmo de s foi o uso de carimbos de data e hora para fornecer uma ordenação total de eventos que era consistente com a ordem causal. Essa percepção pode ter sido brilhante. Tendo percebido isso, tudo o resto era trivial. Como Thomas e Johnson não entenderam exatamente o que estavam fazendo, não entenderam o algoritmo corretamente; seu algoritmo permitiu um comportamento anômalo que violava essencialmente a causalidade. Eu escrevi rapidamente uma nota curta apontando isso e corrigindo o algoritmo.

Eu aprimorei esta resposta com uma resposta extensa no MathOverflow à pergunta da comunidade de Gil Kalai na wiki "[O que é] um livro que você gostaria de escrever ".

A resposta estendida procura vincular questões fundamentais no TCS e QIT a questões práticas na cura e medicina regenerativa.

• A geometria de Joseph M. Landsberg e a complexidade da multiplicação de matrizes (2008)

• A teoria simplética de Alvaro Pelayo e San Vu Ngoc de sistemas hamiltonianos completamente integráveis

A arena matemática para a pesquisa de Landsberg é variedades secantes de variedades de Segre , enquanto a arena para a pesquisa de Pelayo e Ngoc são variedades simpléticas quadridimensionais ... leva um tempo para perceber que essas duas arenas são estados de produtos matriciais, vistos respectivamente de uma perspectiva computacional (Landsburg) e uma perspectiva geométrica (Palayo e Ngoc). Além disso, Palayo e Ngoc incluem em sua pesquisa uma discussão sobre o estudo semi-clássico de Babelon, Cantini e Douçot do modelo de Jaynes-Cummings (observando que o modelo de Jaynes-Cummings é freqüentemente encontrado na literatura de física da matéria condensada e computação quântica )

Cada uma dessas referências vai longe para iluminar as outras. Em particular, tem sido útil em nossos próprios cálculos dinâmicos de rotação apreciar que os espaços de estados quânticos descritos de várias maneiras na literatura como estados de rede tensorial, estados de produtos matriciais e variedades secantes de variedades Segre são ricamente dotados com singularidades cuja estrutura algébrica, simplética e riemanniana é atualmente muito incompleta (como a revisão de Pelayo e Ngoc).

Para nossos propósitos de engenharia, a abordagem de Landsburg / geometria algébrica , na qual o espaço de estados da dinâmica quântica é visto como uma variedade algébrica e não como um espaço vetorial, está emergindo como a mais matematicamente natural. Isso é surpreendente para nós, mas, em comum com muitos pesquisadores, descobrimos que o conjunto de ferramentas da geométrica algébrica é gratificantemente eficaz na validação e aceleração de simulações quânticas práticas.

Atualmente, os simuladores quânticos desfrutam da circunstância intrigante de que grandes simulações numéricas quânticas muitas vezes apresentam desempenho muito melhor do que temos qualquer motivo conhecido para esperar. Quando matemáticos e físicos chegarem a um entendimento compartilhado, essa perplexidade certamente diminuirá e o prazer certamente permanecerá. Boa! :)

Algoritmos de desenho de gráficos baseados em força são outro exemplo. A idéia é considerar cada aresta como uma mola e o layout dos nós do gráfico corresponde a encontrar equilíbrio na coleção de molas.

Grande parte da matemática que usamos foi originalmente inventada para resolver problemas de física. Exemplos incluem cálculo (gravidade newtoniana) e séries de Fourier (equação do calor).

Existe um artigo recente que estabelece a conexão entre a Segurança do computador e o 2º princípio da termodinâmica.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166

O conceito de potencial está relacionado a muitas áreas diferentes da física. Em cs, o potencial é usado na análise amortizada de estruturas de dados. Podemos ver como cada etapa afeta a entropia do sistema e, portanto, obter um custo médio (amortizado) de uma operação com uma determinada estrutura de dados. Isso deu origem a muitas estruturas de dados teoricamente melhores, como a pilha de fibonacci.

para adicionar / preencher alguma lacuna nas excelentes respostas / cobertura atuais - parece haver uma forte conexão entre o TCS e a termodinâmica de várias maneiras que ainda não foram totalmente exploradas, mas são as fronteiras da pesquisa ativa. existe um ponto de transição associado ao SAT, mas parece que possivelmente há pontos de transição associados a outras (ou mesmo a todas) classes de complexidade. o ponto de transição SAT está associado a uma diferença entre instâncias "fáceis" (P) e "difíceis" (NP), mas é possível que todos os limites de classes de complexidade devam levar à mesma propriedade semelhante a um ponto de transição.

considere uma máquina de Turing. ele já mede sua operação em dimensões normalmente físicas de "tempo" e "espaço". mas observe que, aparentemente, ele também faz uma unidade de "trabalho" movendo-se de quadrado em quadrado e fazendo uma transição. em física, a unidade de trabalho é Joules, que também é uma medida de energia. portanto, parece que as classes de complexidade têm alguma relação com os níveis, limites ou regimes de energia.

a teoria da mecânica quântica vê cada vez mais o espaço e o próprio tempo, o universo, como uma espécie de sistema de computação. parece que possui algumas "unidades mínimas de computação" intrínsecas à sua natureza, provavelmente relacionadas ao comprimento da prancha. portanto, o exame de máquinas mínimas de Turing quanto a problemas também implica e se relaciona com sistemas físicos / energéticos mínimos ou mesmo volumes de espaço necessário. [3]

Além disso, o conceito-chave de entropia aparece repetidamente no TCS e na física / termodinâmica e pode ser um princípio unificador, com pesquisas ainda mais ativas revelando sua natureza subjacente. [1,2]

[1] entropia em teoria da informação , wikipedia

[2] qual é a definição de CS da entropia , stackoverflow

[3] Qual é o volume de informações? tcs.se