Um novo mapa traça os limites da computação
Um grande avanço revela conexões profundas entre as classes de problemas que os computadores podem —e não podem— possivelmente fazer. À primeira vista, a grande novidade da conferência de verão sobre a teoria da computação pareceu ser uma decepção. Por mais de 40 anos, pesquisadores tentaram encontrar uma maneira melhor de comparar duas sequências arbitrárias de caracteres, como as longas sequências de letras químicas dentro das moléculas de DNA. O algoritmo mais usado é lento e não é tão inteligente: ele segue passo a passo as duas listas, comparando valores em cada etapa. Se um método melhor para calcular essa "distância de edição" pudesse ser encontrado, os pesquisadores seriam capazes de comparar rapidamente genomas completos ou grandes conjuntos de dados, e cientistas da computação teriam uma nova ferramenta poderosa com a qual poderiam tentar resolver problemas adicionais no campo. No entanto, em um artigo apresentado no ACM Symposium on Theory of Computing, doi...