Exemplos em que o insight da geometria foi útil para resolver algo completamente não-geométrico

28

Uma das coisas boas de ter evoluído em um universo com três dimensões espaciais é que desenvolvemos habilidades de resolução de problemas referentes a objetos no espaço. Assim, por exemplo, podemos pensar em um trigêmeo de números como um ponto em 3-d e, portanto, computação sobre trigêmeos de números como computação sobre pontos em 3-d, que podem ser resolvidos usando nossa intuição sobre o espaço. Isso parece sugerir que às vezes seja possível resolver um problema completamente não geométrico usando técnicas da geometria. Alguém conhece esses exemplos?

Obviamente, os termos 'geométrico' e 'não geométrico' são um pouco vagos aqui. Pode-se argumentar que qualquer problema geométrico não é realmente geométrico se você substituir todos os pontos por suas coordenadas. Mas intuitivamente, a definição é clara. Digamos que chamamos de algo geométrico se considerarmos enviar um artigo sobre isso para o SoCG.

Vinayak Pathak
fonte
3
É claro que o avô disso é a abordagem P vs NP descrita por Mulmuley, que é puramente geométrica. Mas ainda não se mostrou útil. A prova que separa P do NC sem operações bit a bit é, no entanto, uma prova não geométrica que usa argumentos geométricos. Eu acrescentaria que, mas eu tenho fornecido muitas respostas já :)
Suresh Venkat
abundância de tais exemplos podem ser encontrados nas provas sem seção de palavras da American Mathematical Monthly
Arjang

Respostas:

24

Mais alguns exemplos:

Sleator, Thurston e Tarjan usaram uma representação geométrica de árvores como partições de polígonos e geometria hiperbólica, para provar limites inferiores para rotação binária de árvores . (Além disso, acredito que o histórico de uma árvore de pesquisa binária dinâmica pode ser representado como uma tetraedro.)

A redução do ancestral menos comum para o alcance de consultas mínimas , devido a Berkman e Vishkin, relaciona um problema de estruturas de dados em árvores a um problema geométrico indiscutível. (e obrigado pelo artigo David)

A redução de um problema de programação para o conjunto independente de peso máximo de retângulos paralelos ao eixo [1] ou a redução de um problema de programação diferente para a cobertura do conjunto geométrico [2] pode se qualificar.

A redução do maior problema de subsequência comum para encontrar camadas de máximos é bem conhecida (ou seja, estou com preguiça de procurar quem realmente pensou nisso).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor e Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. A geometria da programação, FOCS 2010.

[editar mais tarde] Mais alguns casos em que uma visão "geométrica" ​​parecia surpreendente (embora os padrões "submissão ao SoCG" ou "faça algo para visualizar" provavelmente não sejam atendidos):

topologia algébrica aplicada a limites inferiores para computação distribuída

incorporando computabilidade na dimensão Hausdorff

definindo uma noção de distância para grupos, depois volume e, em seguida, crescimento de volume em função da distância, usando "crescimento polinomial"

Ken Clarkson
fonte
2
O artigo de Nikhil é um exemplo muito interessante, que de alguma maneira eu esqueci.
Sasho Nikolov
3
Bem-vindo ao cstheory, Ken :)
Suresh Venkat
1
Nobody seems to mention the planar separator theorem... Which turns out to be an easy consequence of Koebe theorem.
Sariel Har-Peled
2
Estou surpreso que ninguém tenha mencionado a equivalência de otimização e separação para programação linear e seu impacto na otimização combinatória. O livro de Grotschel, Lovasz e Schrijver é intitulado "Algoritmos geométricos e otimização combinatória".
Chandra Chekuri
1
Os dois documentos importantes que relacionam a topologia algébrica à computação distribuída (que ganhou o Prêmio Gödel de 2004) são: * Maurice Herlihy e Nir Shavit, "A Estrutura Topológica da Computabilidade Assíncrona", JACM 46, 6 (1999). * Michael Saks e Fotios Zaharoglou, "O acordo k-set sem espera é impossível: a topologia do conhecimento público", SIAM J. Computing 29, 5 (2000).
Diego de Estrada
15

É claro que uma resposta muito melhor do que a anterior é o uso da teoria de incorporação métrica para resolver cortes mais esparsos. Um passo importante na solução do problema de corte mais esparso foi a percepção de que ele poderia ser aproximado, encontrando uma boa incorporação de uma métrica geral em um espaço 1 .

Suresh Venkat
fonte
Você poderia citar o jornal?
usuário
1
@ usuário aqui você vai.
Suresh Venkat
12

Eles também foram mencionados em outro lugar, mas um exemplo que eu gosto é: classificar com informações parciais é o problema de encontrar uma extensão linear desconhecida fixa de um poset, dado o poset e usar o número de consultas de comparação o mais próximo possível da teoria da informação limite inferior (isso é apenas uma classificação quando o número de comparações é a medida da complexidade crítica e algumas comparações são feitas de graça). A existência de estratégias de comparação ótimas (até constantes) foi comprovada por Saks e Kahn, usando as propriedades do pólipo de ordem, um polítopo especial associado a um poset (você pode encontrar uma excelente exposição no livro Palestras sobre geometria discreta de Matousek). O primeiro algoritmo de tempo polinomial (de Kahn e Kim) que calcula uma estratégia de comparação ótima (até constante) novamente usou as propriedades do polítopo da ordem, bem como o polítopo estável do gráfico de incomparabilidade do poset de entrada.

Sasho Nikolov
fonte
11

Existe um artigo relativamente recente de Demaine et al. Que usa uma representação geométrica de árvores de busca binária para avançar o estado da arte em otimização dinâmica. Estou sendo um pouco vago aqui, porque eles não resolvem a conjectura de DO: mas reforçam alguns limites e dão novas idéias que parecem vir da formulação geométrica.

Suresh Venkat
fonte
11

Eu não acho que existem exemplos de tais coisas. Exceto para programação linear, programação semi-definida, números complexos, grandes frações de aprendizado de máquina etc. A verdadeira questão é http://www.youtube.com/watch?v=ExWfh6sGyso .

Sariel Har-Peled
fonte
5
qualquer resposta envolvendo Monty Python merece pontos extras :)
Suresh Venkat
9

No ano passado, houve um bom artigo na POPL, EigenCFA: Accelerating flow analysis with GPUs , que representava termos lambda como matrizes e depois usava GPUs para executar rapidamente análises de fluxo de dados nelas.

O artigo não apontou isso explicitamente, mas o que eles estavam basicamente fazendo era explorar a estrutura categórica dos espaços vetoriais para representar árvores. Ou seja, na teoria comum dos conjuntos, uma árvore (de certa altura fixa) é uma união aninhada e aninhada de produtos cartesianos.

No entanto, os espaços vetoriais também possuem produtos e somas diretos, para que você possa representar uma árvore como um elemento de um espaço vetorial adequado. Além disso, produtos diretos e somas diretas coincidem com espaços vetoriais - ou seja, eles têm a mesma representação. Isso abre as portas para implementações paralelas: como as representações físicas são as mesmas, muitas ramificações e perseguições por ponteiros podem ser eliminadas.

Também explica por que a análise do fluxo de dados é em tempo cúbico: está computando vetores próprios!

Neel Krishnaswami
fonte
Você tem algum outro exemplo em que essa árvore para truque de espaços vetoriais é usada? O papel EigenCFA requer muitos antecedentes para entender.
Chao Xu
Se bem entendi, a relação árvore / vetor está apenas convertendo a árvore em vetor, listando os rótulos do percurso de pré-encomenda da árvore?
Chao Xu
8

Na rede, os roteadores usam TCAMs (memórias ternárias endereçáveis ​​ao conteúdo - em outras palavras, memória endereçável ao conteúdo com um pouco de importância) para classificar o tráfego. As entradas em um TCAM geralmente são regras multidimensionais de correspondência de prefixo: por exemplo, (101 *, 11 *, 0 *) corresponde a qualquer pacote em que o primeiro campo de cabeçalho comece com 101 e o segundo campo de cabeçalho comece com 11 (e etc.) um pacote não corresponde à primeira regra, continua com a segunda e assim sucessivamente até que uma regra correspondente seja encontrada.

dRd+1d+1Rd+1dd+1

Para pessoas que trabalham em rede, essa interpretação é útil para entender o que um conjunto específico de regras faz. Para os teóricos, existem outros usos interessantes. De acordo com Algorithms for Packet Classification de Gupta e McKeown, a interpretação geométrica nos permitiu estabelecer rapidamente limites inferiores e superiores para o problema de classificação de pacotes. Sei que o trabalho sobre a minimização de regras do TCAM (encontrar o menor número de regras que preserva a semântica) também se beneficiou de uma abordagem geométrica. Há muitas referências que eu poderia dar para isso, mas a que pode ser mais útil para você é o artigo SODA 2007 da Applegate, et al., Compactando imagens retilíneas e minimizando as listas de controle de acesso. Eles provam que minimizar uma variante mais geral das regras de correspondência de prefixo acima é difícil para o NP e conectam-no (novamente) a imagens bonitas de retângulos para resolver o problema!

Christopher Monsanto
fonte
8

Estou surpreso que ninguém tenha dito o algoritmo euclidiano por encontrar o maior fator comum entre dois números. Você pode lidar com o problema desenhando um retângulo axb e, em seguida, subdividir o retângulo pelo quadrado criado pelo lado menor, repetir para o retângulo restante, continuar repetindo pelos retângulos restantes até encontrar um quadrado que possa dividir igualmente o retângulo restante (consulte gif animado na página Algoritmo Euclidiano).

Maneira bastante elegante de tentar descobrir como as coisas funcionam, IMO.

Doug T.
fonte
3
Eu acho que Euclides argumentaria que os números não se qualificam como "completamente não geométricos"!
Jeffε
7

Provavelmente, existem muitos exemplos para listar, mas um exemplo clássico (destacado por Aigner e Ziegler como uma " Prova do Livro ") é o uso por Lovász de uma representação geométrica para resolver um problema na capacidade de Shannon. Embora a prova tenha sido publicada em 1979 e tenha resolvido uma questão em aberto em 1956, isso continua sendo o estado da arte.

RJK
fonte
6

Relação de códigos de correção de erros com reticulados, empacotamento de esferas etc. (por exemplo, livro de Conway e Sloane). No entanto, a relação é tão forte que não fica claro se devo chamar os códigos de correção de erros "completamente não geométricos" depois disso ...

Alex 'qubeat'
fonte
4

Técnicas de redução de treliça , como LLL ou PSLQ , são altamente geométricas e resolvem problemas da teoria dos números puros, como aproximação linear diofantina e detecção de relação de número inteiro.

ZZ

user834
fonte
1

kk

Obviamente, a prova é mais topológica do que geométrica, mas em baixa dimensão, possui uma imagem geométrica clara. Que eu saiba, não existe prova puramente combinatória (isto é, uma prova que você possa explicar a uma pessoa que se recusa a ouvir algo sobre topologia).

Andrew Ryzhikov
fonte
-1

A máquina de vetores de suporte no aprendizado de máquina provavelmente se qualifica.

mirror2image
fonte
-2

Existem técnicas de geometria computacional para resolver programação linear. Geometria computacional: algoritmos e aplicativos tem um capítulo simples e agradável sobre isso.

Luca Zanetti
fonte
2
Mas a programação linear - "Encontre o ponto mais baixo neste poliedro" - é explicitamente geométrica.
Jeffε
-3

Um Integral Definido de uma função pode ser representado como a área assinada da região delimitada por seu gráfico.

George Polevoy
fonte
4
Correto, exceto que "pode ​​ser representado como" deve ser escrito "é".
Jeffε 14/05