Otimização com água e sabão

Ano passado fui pela primeira vez à Estação Ciência, em São Paulo, e fiquei espantado com a qualidade. Eu já visitei o Natural History Museum de Londres, e o American Museum of Natural History em New York, então eu digo, com conhecimento de causa, que a Estação Ciência não fica nada a dever aos museus de ciência do primeiro mundo. Tem dinossauros, planetário, simulador de terremoto, e até simulador de tsunami (que não tinha nos museus lá de cima).

Na verdade, o museu brasileiro tem uma vantagem sobre os outros. Por lá, a média é de, mais ou menos, uns quarenta visitantes por guia, e aqui a média é de três guias por visitante! Se você tiver bastante tempo pra visitar, os guias irão lhe dar explicações extremamente detalhadas das exposições.

A minha predileta foi na seção de matemática experimental, onde fizemos a experiência do sabão. Você pega duas placas paralelas quaisquer, coloca quatro pregos nelas, e mergulha num balde de água com sabão. Eu estava esperando que o sabão grudasse nos pregos e fizesse um quadrilátero, mas na verdade o que ele faz é uma estrutura em duplo Y:

(Você pode fazer em casa esse experimento, mas para melhores resultados, coloque um pouco de glicerina na água. Experimente também com outras quantidades de pregos, e com figuras tridimensionais).

A explicação é que o sabão, como bom sistema físico, vai procurar a posição de energia mínima, que nesse caso é equivalente a minimizar a soma dos comprimentos da película. Anedoticamente, esse problema é conhecido como o problema da estrada (como ligar quatro cidades com estradas, gastando a menor quantidade possível de asfalto?), e a solução ótima é conhecida como Steiner Tree.

À primeira vista pode parecer que a Steiner Tree é equivalente à Minimum Spanning Tree, mas não é. Pra calcular a spanning tree, você só pode usar os pontos do grafo, já na Steiner tree você pode adicionar pontos novos. Isso faz uma diferença enorme na complexidade: existem algoritmos quase lineares para resolver a spanning tree, já a Steiner tree é NP-completa.

Na verdade, há quem diga que isso é uma prova de que P=NP, como os autores desse paper no Arxiv. Segundo eles, existe um computador analógico feito com sabão que resolve um problema NP-completo em tempo polinomial, logo P=NP :)

Pra quem quiser brincar com Steiner trees, o problema ELC do spoj pede pra resolver uma instância com 3k pontos. Como isso é demais para um brute force, você vai ter que aproximar: por exemplo, iterando a partir de uma spanning tree; ou então, calculando a triangulação de Delaunay e depois resolvendo a Steiner tree local de cada triângulo.