Os cientistas da computação querem saber quantas etapas um determinado algoritmo requer. Por exemplo, qualquer algoritmo native que possa resolver o problema do roteador com apenas duas cores deve ser incrivelmente ineficiente, mas é possível encontrar um algoritmo native muito eficiente se você puder usar três.
Na palestra em que Bernshteyn participou, o palestrante discutiu esses limites para diferentes tipos de problemas. Um dos limites, percebeu ele, parecia muito com um limite que existia no mundo da teoria descritiva dos conjuntos – sobre o número de cores necessárias para colorir certos gráficos infinitos de uma forma mensurável.
Para Bernshteyn, parecia mais do que uma coincidência. Não é só que os cientistas da computação também são como bibliotecários, arquivando problemas com base na eficiência com que seus algoritmos funcionam. Não period apenas que esses problemas também pudessem ser escritos em termos de gráficos e cores.
Talvez, pensou ele, as duas estantes tivessem mais em comum do que isso. Talvez a ligação entre estes dois campos tenha sido muito, muito mais profunda.
Talvez todos os livros e suas estantes fossem idênticos, apenas escritos em idiomas diferentes — e precisando de um tradutor.
Abrindo a porta
Bernshteyn decidiu tornar esta ligação explícita. Ele queria mostrar que todo algoritmo native eficiente pode ser transformado em uma forma mensurável de Lebesgue de colorir um gráfico infinito (que satisfaça algumas propriedades adicionais importantes). Ou seja, uma das prateleiras mais importantes da ciência da computação equivale a uma das prateleiras mais importantes da teoria dos conjuntos (no topo da hierarquia).
Ele começou com a classe de problemas de rede da palestra sobre ciência da computação, concentrando-se em sua regra geral – que o algoritmo de qualquer nó usa informações apenas sobre sua vizinhança native, independentemente de o gráfico ter mil nós ou um bilhão.
Para funcionar corretamente, tudo o que o algoritmo precisa fazer é rotular cada nó em uma determinada vizinhança com um número exclusivo, para que possa registrar informações sobre nós próximos e fornecer instruções sobre eles. Isso é bastante fácil de fazer em um gráfico finito: basta atribuir a cada nó do gráfico um número diferente.
