Resultados de física no TCS?

42

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.

Joe Fitzsimons
fonte
9
Não sei se sistemas complexos contam, então ainda não estou postando como resposta. é 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, usando armas da estatística e da termodinâmica. Se foi invadido pela física é uma história diferente.
Suresh Venkat
Eu acho que isso conta.
Joe Fitzsimons 10/10
ver também como é a física / CS ficando Estados physics.se
vzn

Respostas:

26

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.

Dave Clarke
fonte
supercooldave: Meu entendimento limitado era que o recozimento simulado evita apenas os mínimos locais que são "suficientemente rasos". Isso está correto?
Joshua Grochow
1
@ Josué: em geral, o recozimento simulado nem sempre consegue evitar o mínimo local. Ele sempre pode ficar preso no lugar errado. Alguma experimentação é necessária para encontrar um bom ponto de partida e assim por diante.
Dave Clarke
1
Obviamente, é importante notar que o recozimento 'real' nem sempre evita os mínimos locais! Defeitos (no sentido da matemática-física) não são inéditos.
Steven Stadnicki 15/07
Se a diminuição da temperatura ocorrer exponencialmente lentamente, o recozimento simulado obterá muitas propriedades desejáveis ​​de otimização global. Obviamente, ele também ganha um tempo de execução exponencial.
21412 Elliot JJ
23

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.

Peter Shor
fonte
2
Uma coisa que me impressionou nessa área é que parece ser mais a comunidade teórica da física nas informações quânticas do que a comunidade TCS (se é que podemos realmente fazer essa distinção) que parece estar interessada nessas técnicas.
Joe Fitzsimons
5
Eu definitivamente concordo. Tentei fazer com que um estudante de graduação se interessasse por eles desde o início, mas a reação dele foi "bleah ... esses são apenas métodos de aproximação heurística, e você não pode dizer nada de rigor sobre eles". Obviamente, isso acabou incorreto.
Peter Shor
1
(@Shor) Gostei muito desta resposta e forneci uma resposta complementar com várias outras referências --- pelo menos uma delas (a pesquisa Geometry de Joseph Landsburg em 2008 e a complexidade da multiplicação de matrizes ) está definitivamente no final do TCS o espectro. cstheory.stackexchange.com/questions/2074/…
John Sidles
20

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.

Suresh Venkat
fonte
Estou desenvolvendo um forte interesse em redes e análise de redes sociais. Você tem alguma referência?
18711 Dave McMillan -
2
Hmm. É melhor começar com o livro Kleinberg / Easley (que é um bom texto para estudantes de graduação). Então você poderia trabalhar para a frente e para trás do trabalho por Aaron Clauset e Mark Newman
Suresh Venkat
19

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.

S Huntsman
fonte
Eu também mencionaria a computação do DNA como uma área de sobreposição, embora com conexões mais tênues com a física teórica em si.
S Huntsman
Eu tinha mais em mente áreas em que o TCS se beneficiava com resultados em física, e não o contrário.
Joe Fitzsimons 10/10
7
Bem, então (embora possa ser considerado implícito ou relacionado a algumas outras coisas mencionadas nesta página) eu seria negligente em não mencionar a teoria da computação reversível, mais notavelmente o círculo de idéias nascido do trabalho de Landauer, que influenciou muitos outros. áreas além da computação quântica.
S Huntsman
Para comentar a resposta de Suresh (não há representante suficiente para comentar lá): tem havido muitas aplicações frutíferas de idéias na física para a análise da dinâmica nas redes. Como exemplo, lembro-me de um artigo discutindo evidências de que o tráfego TCP exibia criticidade auto-organizada. Como outro exemplo, alguns pesquisadores (inclusive eu) trabalharam na aplicação de idéias da física (não apenas da entropia) para caracterizar o tráfego de rede para detecção de anomalias. Obviamente, isso deixa o T fora do TCS.
S Huntsman
17

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

Andrej Bauer
fonte
3
Sim, na verdade, ouvi Prakash falar sobre isso em sua oficina em Barbados. Trabalho realmente interessante. Fiquei, no entanto, com a impressão de que ele também tinha formação em física. Além disso, certamente existem contribuições em ambas as direções. Acontece que eu estava particularmente interessado em descobrir uma direção em particular. Presumivelmente, perguntar sobre a influência do TCS na física seria mais adequado para um site de física, uma vez que as pessoas no campo que adaptam idéias de um segundo campo estão melhor posicionadas para determinar quais delas tiveram um impacto significativo no primeiro.
Joe Fitzsimons
13

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.

RJK
fonte
11

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 .

Neel Krishnaswami
fonte
2
E a combinatória analítica (Flajolet e Sedgewick)?
RJK
11

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.

Yaroslav Bulatov
fonte
9

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.

Huck Bennett
fonte
Caramba, acabei de perceber que Joe referenciou isso em sua pergunta original. Espero que isso seja um pouco complicado.
Huck Bennett
9

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.

Martin Schwarz
fonte
9

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.


Essa resposta estende a resposta de Peter Shor , que discute os papéis dos estados de produtos matriciais no TCS e na física. Duas pesquisas recentes no Boletim da AMS são relevantes para os estados dos produtos matriciais, e ambas são bem escritas, livres de restrições de parede de pagamento e razoavelmente acessíveis a não especialistas:

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! :)

John Sidles
fonte
8

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.

Dave Clarke
fonte
Eu não pensaria isso particularmente no TCS, mas é uma técnica tão legal que você recebe +1 de mim. Afinal, algumas áreas da ciência da computação são fortemente dependentes da física (isto é, SIGGRAPH).
Joe Fitzsimons
Os gráficos são certamente TCS. E eles precisam ser atraídos. E David Eppstein faz desenho gráfico. (Este é o meu argumento convincente.)
Dave Clarke
Ok, eu vou aceitar esse argumento.
Joe Fitzsimons
Esta técnica é um participante importante no desenho gráfico. definitivamente vale a pena mencionar
Suresh Venkat
Ótimo exemplo! +1 de mim
George
2

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).

Warren Schudy
fonte
6
De maneira semelhante, Belkin, Narayanan e Niyogi (FOCS '06, dx.doi.org/10.1109/FOCS.2006.34 ) usaram análises matemáticas do estudo de fluxo e difusão de calor para fornecer um algoritmo aleatório rápido para calcular a área superficial de um corpo convexo em n dimensões.
arnab
2
bom exemplo. embora isso seja um exemplo de física ou matemática? :)
Suresh Venkat
1

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.

Nate
fonte
-1

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

vzn
fonte
1
Você percebe que eu respondi à pergunta tcs.se, certo?
Joe Fitzsimons
Gostaria de entender por que essa pergunta foi rebaixada. A votação sem explicação não ajuda ninguém, já que os motivos podem ser não técnicos. Entendo que o OP estava ciente de alguns ou todos esta resposta, mas desde que ele não mencionou isso na questão ... @JoeFitzsimons cc
babou