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, dois pesquisadores do Massachusetts Institute of Technology apresentaram uma prova matemática de que o melhor algoritmo atual era "ótimo" - em outras palavras, que encontrar uma maneira mais eficiente de computar a distância era matematicamente impossível. O Boston Globe celebrou a conquista dos pesquisadores da cidade natal com uma manchete que dizia: "Por 40 anos, os cientistas da computação procuraram por uma solução que não existe".
Mas os pesquisadores ainda não estão prontos para registrar a hora da morte. Uma lacuna significativa permanece. O resultado da impossibilidade só é verdadeiro se outra afirmação famosa e não comprovada, chamada hipótese do tempo exponencial forte (SETH), também for verdadeira. A maioria dos pesquisadores de complexidade computacional assume que este é o caso - incluindo Piotr Indyk e Artūrs Bačkurs, do MIT, que publicaram a descoberta da distância de edição —mas a validade de SETH ainda é uma questão em aberto. Isso faz com que o artigo sobre o problema da distância de edição pareça uma versão matemática do legendário relato da morte de Mark Twain: muito exagerado.
A confusão da mídia sobre a distância de edição reflete uma obscuridade na própria profundidade da teoria da complexidade, onde matemáticos e cientistas da computação tentam mapear o que é e o que não é possível computar como se fossem exploradores de mar profundo mapeando o fundo de uma trincheira oceânica. Esse terreno algorítmico é tão vasto —e pouco compreendido - quanto o fundo do mar real, disse Russell Impagliazzo, um teórico da complexidade que formulou a hipótese do tempo exponencial com Ramamohan Paturi em 1999. “A analogia é boa”, disse ele. “Os oceanos são onde a dureza computacional é. O que estamos tentando fazer é usar ferramentas mais refinadas para medir a profundidade do oceano em diferentes lugares.”
De acordo com Ryan Williams, um teórico de complexidade computacional da Universidade de Stanford, uma compreensão imprecisa de conceitos teóricos como o SETH pode ter consequências no mundo real. "Se uma agência de financiamento ler essa [manchete do Boston Globe] e levar isso a sério, então não vejo nenhuma razão para que eles possam financiar o trabalho na área de edição novamente", disse ele. “Para mim, isso é um pouco perigoso.” Williams rejeita a conclusão de que um algoritmo de edição-distância melhor é impossível, já que ele acredita que SETH é falso. “Minha posição [na SETH] é um pouco controversa”, ele admite, “mas não há um consenso. É uma hipótese, e eu não acredito que seja verdade.SETH é mais que uma mera brecha no problema da distância de edição. Ele incorpora várias conexões profundas que unem os problemas mais difíceis na computação. A ambigüidade sobre sua verdade ou falsidade também revela as práticas básicas da ciência da computação teórica, nas quais a matemática e a lógica muitas vezes apresentam “evidências fortes”, ao invés de provas, de como os algoritmos se comportam em um nível fundamental.Seja assumindo a validade de SETH ou, no caso de Williams, tentando refutá-la, os teóricos da complexidade estão usando essa hipótese arcana para explorar duas versões diferentes de nosso universo: uma em que respostas precisas a problemas difíceis permanecem enterradas para sempre como agulhas dentro de um vasto palheiro, e aquele em que pode ser possível acelerar a busca de conhecimento sempre de forma leve.
Quão difícil isso pode ser?
Teoria da complexidade computacional é o estudo de problemas. Especificamente,
ele tenta classificar o quão “duro” eles são - isto é, quão
eficientemente uma solução pode ser computada sob condições realistas.SETH
é uma suposição de dureza sobre um dos problemas centrais na ciência da
computação teórica: satisfatibilidade booleana, que é abreviada como
SAT. Em seu rosto, o SAT parece simples. Se
você tem uma fórmula contendo variáveis que podem ser configuradas
como verdadeiras ou falsas em vez de valores numéricos, é possível
definir essas variáveis de tal forma que a fórmula produza “true”? A
tradução do SAT para linguagem simples, no entanto, revela sua
complexidade metamatemática: Essencialmente, ele pergunta se um problema
genérico (conforme modelado por uma fórmula lógica) é solucionável.Tanto
quanto os cientistas da computação sabem, o único método de propósito
geral para encontrar a resposta correta para um problema de SAT é tentar
todas as configurações possíveis das variáveis, uma por uma. A quantidade de tempo que essa abordagem exaustiva ou de força bruta leva depende de quantas variáveis existem na fórmula. À
medida que o número de variáveis aumenta, o tempo necessário para
pesquisar todas as possibilidades aumenta exponencialmente. Para os teóricos da complexidade e os projetistas de algoritmos, isso é ruim. (Ou, tecnicamente falando, difícil.)SETH leva essa situação de mal a pior. Isso
implica que é impossível encontrar um algoritmo de propósito geral
melhor para o SAT - mesmo um que apenas melhore a busca de força bruta
por uma pequena quantidade.Os
limites computacionais do SAT são importantes porque o SAT é
matematicamente equivalente a milhares de outros problemas relacionados à
busca e otimização. Se
fosse possível encontrar um algoritmo eficiente de propósito geral para
qualquer um desses chamados problemas “NP-completos”, todos os demais
seriam instantaneamente desbloqueados também.Essa
relação entre problemas NP-completos é central para a conjectura “P
versus NP”, o mais famoso problema não solucionado da ciência da
computação, que procura definir os limites da computação em termos
matemáticos. (A
versão informal: se P é igual a NP, poderíamos calcular rapidamente a
resposta verdadeira a quase todas as perguntas que quiséssemos, contanto
que soubéssemos como descrever o que queríamos encontrar e pudéssemos
reconhecê-lo facilmente assim que o víssemos, como um A
grande maioria dos cientistas da computação acredita que P não é igual a
NP.) O problema P versus NP também ajuda a desenhar uma linha informal
entre procedimentos computacionais tratáveis (“fáceis”) e intratáveis
(“hard”).SETH
aborda uma questão em aberto sobre a dureza dos problemas NP-completos
sob as piores condições: O que acontece quando o número de variáveis
em uma fórmula SAT fica maior e maior? A resposta da SETH é dada em termos bem nítidos: você nunca fará melhor do que uma busca exaustiva. De
acordo com Scott Aaronson, especialista em complexidade computacional
do MIT, “é como 'P não é igual a NP' nos turbocompressores”.
O lado positivo do impossívelParadoxalmente, é a nitidez do SETH sobre o que não pode ser feito, o que o torna tão útil para pesquisadores de complexidade. Ao assumir que certos problemas são computacionalmente intratáveis sob restrições precisas, os pesquisadores podem fazer inferências imediatas sobre as propriedades de outros problemas, mesmo aqueles que parecem não estar relacionados no início. Essa técnica, combinada com outra chamada redução (que pode traduzir uma questão para a linguagem matemática de outra), é uma maneira poderosa para os teóricos da complexidade examinarem as características dos problemas. De acordo com Impagliazzo, a precisão da SETH, comparada com a de outras conjecturas de dureza (como P não igual a NP), é um pouco como a diferença entre um bisturi e um taco. "Estamos tentando usar o SETH para formar conexões mais delicadas entre problemas", disse ele.SETH fala diretamente sobre a dureza dos problemas NP-completos, mas algumas reduções surpreendentes ligaram-no a problemas importantes na classe de complexidade P - o território dos chamados problemas fáceis ou eficientemente solúveis. Um desses problemas da classe P é a distância de edição, que calcula o menor número de operações (ou edições) necessárias para transformar uma seqüência de símbolos em outra. Por exemplo, a distância de edição entre livro e verso é 2, porque um pode ser transformado em outro com duas edições: Troque o primeiro o por um ae o segundo o por c.Indyk e Bačkurs conseguiram provar uma conexão entre a complexidade da distância de edição e a da k-SAT, uma versão do SAT que os pesquisadores costumam usar nas reduções. O K-SAT é “o problema canônico NP-completo”, disse Aaronson, o que significa que a Indyk poderia usar o SETH e suas suposições pessimistas sobre a dureza do k-SAT para fazer inferências sobre a dureza do problema de distância de edição.O resultado foi surpreendente porque editar distância, embora teoricamente um problema fácil na classe de complexidade P, levaria talvez 1.000 anos para ser executado quando aplicado a tarefas reais como comparar genomas, onde o número de símbolos é de bilhões (em oposição a livro e verso). Descobrir um algoritmo mais eficiente para editar distâncias teria implicações importantes para a bioinformática, que atualmente conta com aproximações e atalhos para lidar com a distância de edição. Mas se a SETH for verdadeira - o que a prova de Indyk e Bačkurs pressupõe - então não há esperança de encontrar um algoritmo substancialmente melhor.A palavra-chave, é claro, é "se". Indyk prontamente admite que seu resultado não é uma prova de impossibilidade incondicional, que é "o santo graal da ciência da computação teórica", disse ele. “Infelizmente, estamos muito, muito longe de provar algo assim. Como resultado, fazemos a próxima melhor coisa ”.Indyk também admite ironicamente que ele estava "recebendo vários tweets" sobre o exagero do Globo em sua realização e Bačkurs. “Uma maneira mais precisa de expressar isso seria que [nosso resultado] é uma forte evidência de que o problema da distância de edição não tem um algoritmo mais eficiente do que o que já temos. Mas as pessoas podem variar em sua interpretação dessa evidência ”.Ryan Williams certamente interpreta de forma diferente. "É uma conexão notável que eles fizeram, mas eu tenho uma interpretação diferente", disse ele. Ele inverte o problema: “Se eu quero refutar o SETH, eu só tenho que resolver a distância de edição mais rapidamente”. E nem mesmo por uma margem que faria uma diferença prática em como os genomas são sequenciados. Se Williams ou qualquer outra pessoa puder provar a existência de um algoritmo de distância de edição que funcione mesmo moderadamente mais rápido que o normal, SETH é história.E enquanto Williams é um dos únicos especialistas tentando refutar SETH, não é uma posição herética a tomar. "Eu acho que é totalmente possível", disse Aaronson. Williams está fazendo progresso: sua pesquisa mais recente refuta outra suposição de dureza intimamente relacionada com a SETH. (Ele está preparando o trabalho para publicação.) Se refutar SETH está escalando o Everest, este último resultado é como chegar ao acampamento base.Mesmo que falsificar SETH “possa ser o resultado da década”, nas palavras de Aaronson, para ouvir Williams dizer, a verdade ou falsidade da SETH não é o ponto. "É quase como se o valor da verdade não fosse tão relevante para mim enquanto estou trabalhando", disse ele. O que ele quer dizer é que o bisturi do SETH tem dois gumes: a maioria dos pesquisadores gosta de provar resultados ao supor que SETH é verdadeira, mas Williams obtém mais influência assumindo que é falso. "Para mim, parece ser uma boa hipótese de trabalho", disse ele. "Desde que eu acredite que é falso, parece que posso fazer muito progresso."
Mesmo que falsificar SETH “possa ser o resultado da década”, nas palavras de Aaronson, para ouvir Williams dizer, a verdade ou falsidade da SETH não é o ponto. "É quase como se o valor da verdade não fosse tão relevante para mim enquanto estou trabalhando", disse ele. O que ele quer dizer é que o bisturi do SETH tem dois gumes: a maioria dos pesquisadores gosta de provar resultados ao supor que SETH é verdadeira, mas Williams obtém mais influência assumindo que é falso. "Para mim, parece ser uma boa hipótese de trabalho", disse ele. "Desde que eu acredite que é falso, parece que posso fazer muito progresso."As tentativas de Williams de refutar o SETH deram frutos consideráveis. Por exemplo, em outubro ele apresentará um novo algoritmo para resolver o problema dos “vizinhos mais próximos”. O avanço surgiu de uma tentativa fracassada de refutar SETH. Dois anos atrás, ele usou uma tática que tentou refutar a SETH e a aplicou ao problema dos “caminhos mais curtos de todos os pares”, uma tarefa de otimização clássica “ensinada em todos os currículos de ciência da computação”, ele disse. Seu novo algoritmo melhorou em estratégias computacionais que não mudaram significativamente desde a década de 1960. E antes disso, outra abordagem abortiva levou Williams a obter uma prova inovadora em um domínio relacionado à ciência da computação chamado complexidade do circuito. Lance Fortnow, um teórico da complexidade e presidente da Escola de Ciência da Computação do Instituto de Tecnologia da Geórgia, chamou a prova de Williams de "o melhor progresso nos limites inferiores do circuito em quase um quarto de século".
À 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, dois pesquisadores do Massachusetts Institute of Technology apresentaram uma prova matemática de que o melhor algoritmo atual era "ótimo" - em outras palavras, que encontrar uma maneira mais eficiente de computar a distância era matematicamente impossível. O Boston Globe celebrou a conquista dos pesquisadores da cidade natal com uma manchete que dizia: "Por 40 anos, os cientistas da computação procuraram por uma solução que não existe".
Mas os pesquisadores ainda não estão prontos para registrar a hora da morte. Uma lacuna significativa permanece. O resultado da impossibilidade só é verdadeiro se outra afirmação famosa e não comprovada, chamada hipótese do tempo exponencial forte (SETH), também for verdadeira. A maioria dos pesquisadores de complexidade computacional assume que este é o caso - incluindo Piotr Indyk e Artūrs Bačkurs, do MIT, que publicaram a descoberta da distância de edição —mas a validade de SETH ainda é uma questão em aberto. Isso faz com que o artigo sobre o problema da distância de edição pareça uma versão matemática do legendário relato da morte de Mark Twain: muito exagerado.
A confusão da mídia sobre a distância de edição reflete uma obscuridade na própria profundidade da teoria da complexidade, onde matemáticos e cientistas da computação tentam mapear o que é e o que não é possível computar como se fossem exploradores de mar profundo mapeando o fundo de uma trincheira oceânica. Esse terreno algorítmico é tão vasto —e pouco compreendido - quanto o fundo do mar real, disse Russell Impagliazzo, um teórico da complexidade que formulou a hipótese do tempo exponencial com Ramamohan Paturi em 1999. “A analogia é boa”, disse ele. “Os oceanos são onde a dureza computacional é. O que estamos tentando fazer é usar ferramentas mais refinadas para medir a profundidade do oceano em diferentes lugares.”
De acordo com Ryan Williams, um teórico de complexidade computacional da Universidade de Stanford, uma compreensão imprecisa de conceitos teóricos como o SETH pode ter consequências no mundo real. "Se uma agência de financiamento ler essa [manchete do Boston Globe] e levar isso a sério, então não vejo nenhuma razão para que eles possam financiar o trabalho na área de edição novamente", disse ele. “Para mim, isso é um pouco perigoso.” Williams rejeita a conclusão de que um algoritmo de edição-distância melhor é impossível, já que ele acredita que SETH é falso. “Minha posição [na SETH] é um pouco controversa”, ele admite, “mas não há um consenso. É uma hipótese, e eu não acredito que seja verdade.SETH é mais que uma mera brecha no problema da distância de edição. Ele incorpora várias conexões profundas que unem os problemas mais difíceis na computação. A ambigüidade sobre sua verdade ou falsidade também revela as práticas básicas da ciência da computação teórica, nas quais a matemática e a lógica muitas vezes apresentam “evidências fortes”, ao invés de provas, de como os algoritmos se comportam em um nível fundamental.Seja assumindo a validade de SETH ou, no caso de Williams, tentando refutá-la, os teóricos da complexidade estão usando essa hipótese arcana para explorar duas versões diferentes de nosso universo: uma em que respostas precisas a problemas difíceis permanecem enterradas para sempre como agulhas dentro de um vasto palheiro, e aquele em que pode ser possível acelerar a busca de conhecimento sempre de forma leve.
Quão difícil isso pode ser?
Teoria da complexidade computacional é o estudo de problemas. Especificamente,
ele tenta classificar o quão “duro” eles são - isto é, quão
eficientemente uma solução pode ser computada sob condições realistas.SETH
é uma suposição de dureza sobre um dos problemas centrais na ciência da
computação teórica: satisfatibilidade booleana, que é abreviada como
SAT. Em seu rosto, o SAT parece simples. Se
você tem uma fórmula contendo variáveis que podem ser configuradas
como verdadeiras ou falsas em vez de valores numéricos, é possível
definir essas variáveis de tal forma que a fórmula produza “true”? A
tradução do SAT para linguagem simples, no entanto, revela sua
complexidade metamatemática: Essencialmente, ele pergunta se um problema
genérico (conforme modelado por uma fórmula lógica) é solucionável.Tanto
quanto os cientistas da computação sabem, o único método de propósito
geral para encontrar a resposta correta para um problema de SAT é tentar
todas as configurações possíveis das variáveis, uma por uma. A quantidade de tempo que essa abordagem exaustiva ou de força bruta leva depende de quantas variáveis existem na fórmula. À
medida que o número de variáveis aumenta, o tempo necessário para
pesquisar todas as possibilidades aumenta exponencialmente. Para os teóricos da complexidade e os projetistas de algoritmos, isso é ruim. (Ou, tecnicamente falando, difícil.)SETH leva essa situação de mal a pior. Isso
implica que é impossível encontrar um algoritmo de propósito geral
melhor para o SAT - mesmo um que apenas melhore a busca de força bruta
por uma pequena quantidade.Os
limites computacionais do SAT são importantes porque o SAT é
matematicamente equivalente a milhares de outros problemas relacionados à
busca e otimização. Se
fosse possível encontrar um algoritmo eficiente de propósito geral para
qualquer um desses chamados problemas “NP-completos”, todos os demais
seriam instantaneamente desbloqueados também.Essa
relação entre problemas NP-completos é central para a conjectura “P
versus NP”, o mais famoso problema não solucionado da ciência da
computação, que procura definir os limites da computação em termos
matemáticos. (A
versão informal: se P é igual a NP, poderíamos calcular rapidamente a
resposta verdadeira a quase todas as perguntas que quiséssemos, contanto
que soubéssemos como descrever o que queríamos encontrar e pudéssemos
reconhecê-lo facilmente assim que o víssemos, como um A
grande maioria dos cientistas da computação acredita que P não é igual a
NP.) O problema P versus NP também ajuda a desenhar uma linha informal
entre procedimentos computacionais tratáveis (“fáceis”) e intratáveis
(“hard”).SETH
aborda uma questão em aberto sobre a dureza dos problemas NP-completos
sob as piores condições: O que acontece quando o número de variáveis
em uma fórmula SAT fica maior e maior? A resposta da SETH é dada em termos bem nítidos: você nunca fará melhor do que uma busca exaustiva. De
acordo com Scott Aaronson, especialista em complexidade computacional
do MIT, “é como 'P não é igual a NP' nos turbocompressores”.O lado positivo do impossívelParadoxalmente, é a nitidez do SETH sobre o que não pode ser feito, o que o torna tão útil para pesquisadores de complexidade. Ao assumir que certos problemas são computacionalmente intratáveis sob restrições precisas, os pesquisadores podem fazer inferências imediatas sobre as propriedades de outros problemas, mesmo aqueles que parecem não estar relacionados no início. Essa técnica, combinada com outra chamada redução (que pode traduzir uma questão para a linguagem matemática de outra), é uma maneira poderosa para os teóricos da complexidade examinarem as características dos problemas. De acordo com Impagliazzo, a precisão da SETH, comparada com a de outras conjecturas de dureza (como P não igual a NP), é um pouco como a diferença entre um bisturi e um taco. "Estamos tentando usar o SETH para formar conexões mais delicadas entre problemas", disse ele.SETH fala diretamente sobre a dureza dos problemas NP-completos, mas algumas reduções surpreendentes ligaram-no a problemas importantes na classe de complexidade P - o território dos chamados problemas fáceis ou eficientemente solúveis. Um desses problemas da classe P é a distância de edição, que calcula o menor número de operações (ou edições) necessárias para transformar uma seqüência de símbolos em outra. Por exemplo, a distância de edição entre livro e verso é 2, porque um pode ser transformado em outro com duas edições: Troque o primeiro o por um ae o segundo o por c.Indyk e Bačkurs conseguiram provar uma conexão entre a complexidade da distância de edição e a da k-SAT, uma versão do SAT que os pesquisadores costumam usar nas reduções. O K-SAT é “o problema canônico NP-completo”, disse Aaronson, o que significa que a Indyk poderia usar o SETH e suas suposições pessimistas sobre a dureza do k-SAT para fazer inferências sobre a dureza do problema de distância de edição.O resultado foi surpreendente porque editar distância, embora teoricamente um problema fácil na classe de complexidade P, levaria talvez 1.000 anos para ser executado quando aplicado a tarefas reais como comparar genomas, onde o número de símbolos é de bilhões (em oposição a livro e verso). Descobrir um algoritmo mais eficiente para editar distâncias teria implicações importantes para a bioinformática, que atualmente conta com aproximações e atalhos para lidar com a distância de edição. Mas se a SETH for verdadeira - o que a prova de Indyk e Bačkurs pressupõe - então não há esperança de encontrar um algoritmo substancialmente melhor.A palavra-chave, é claro, é "se". Indyk prontamente admite que seu resultado não é uma prova de impossibilidade incondicional, que é "o santo graal da ciência da computação teórica", disse ele. “Infelizmente, estamos muito, muito longe de provar algo assim. Como resultado, fazemos a próxima melhor coisa ”.Indyk também admite ironicamente que ele estava "recebendo vários tweets" sobre o exagero do Globo em sua realização e Bačkurs. “Uma maneira mais precisa de expressar isso seria que [nosso resultado] é uma forte evidência de que o problema da distância de edição não tem um algoritmo mais eficiente do que o que já temos. Mas as pessoas podem variar em sua interpretação dessa evidência ”.Ryan Williams certamente interpreta de forma diferente. "É uma conexão notável que eles fizeram, mas eu tenho uma interpretação diferente", disse ele. Ele inverte o problema: “Se eu quero refutar o SETH, eu só tenho que resolver a distância de edição mais rapidamente”. E nem mesmo por uma margem que faria uma diferença prática em como os genomas são sequenciados. Se Williams ou qualquer outra pessoa puder provar a existência de um algoritmo de distância de edição que funcione mesmo moderadamente mais rápido que o normal, SETH é história.E enquanto Williams é um dos únicos especialistas tentando refutar SETH, não é uma posição herética a tomar. "Eu acho que é totalmente possível", disse Aaronson. Williams está fazendo progresso: sua pesquisa mais recente refuta outra suposição de dureza intimamente relacionada com a SETH. (Ele está preparando o trabalho para publicação.) Se refutar SETH está escalando o Everest, este último resultado é como chegar ao acampamento base.Mesmo que falsificar SETH “possa ser o resultado da década”, nas palavras de Aaronson, para ouvir Williams dizer, a verdade ou falsidade da SETH não é o ponto. "É quase como se o valor da verdade não fosse tão relevante para mim enquanto estou trabalhando", disse ele. O que ele quer dizer é que o bisturi do SETH tem dois gumes: a maioria dos pesquisadores gosta de provar resultados ao supor que SETH é verdadeira, mas Williams obtém mais influência assumindo que é falso. "Para mim, parece ser uma boa hipótese de trabalho", disse ele. "Desde que eu acredite que é falso, parece que posso fazer muito progresso."
Mesmo que falsificar SETH “possa ser o resultado da década”, nas palavras de Aaronson, para ouvir Williams dizer, a verdade ou falsidade da SETH não é o ponto. "É quase como se o valor da verdade não fosse tão relevante para mim enquanto estou trabalhando", disse ele. O que ele quer dizer é que o bisturi do SETH tem dois gumes: a maioria dos pesquisadores gosta de provar resultados ao supor que SETH é verdadeira, mas Williams obtém mais influência assumindo que é falso. "Para mim, parece ser uma boa hipótese de trabalho", disse ele. "Desde que eu acredite que é falso, parece que posso fazer muito progresso."As tentativas de Williams de refutar o SETH deram frutos consideráveis. Por exemplo, em outubro ele apresentará um novo algoritmo para resolver o problema dos “vizinhos mais próximos”. O avanço surgiu de uma tentativa fracassada de refutar SETH. Dois anos atrás, ele usou uma tática que tentou refutar a SETH e a aplicou ao problema dos “caminhos mais curtos de todos os pares”, uma tarefa de otimização clássica “ensinada em todos os currículos de ciência da computação”, ele disse. Seu novo algoritmo melhorou em estratégias computacionais que não mudaram significativamente desde a década de 1960. E antes disso, outra abordagem abortiva levou Williams a obter uma prova inovadora em um domínio relacionado à ciência da computação chamado complexidade do circuito. Lance Fortnow, um teórico da complexidade e presidente da Escola de Ciência da Computação do Instituto de Tecnologia da Geórgia, chamou a prova de Williams de "o melhor progresso nos limites inferiores do circuito em quase um quarto de século".
O Mapa e o Território
Além desses benefícios periféricos, atacar o SETH de frente ajuda pesquisadores como Williams a progredir em uma das tarefas centrais da ciência da computação teórica: mapear o território. Assim como sabemos mais sobre a superfície da Lua do que sobre as profundezas de nossos próprios oceanos, os algoritmos estão ao nosso redor e, no entanto, parecem desafiar os esforços dos pesquisadores para entender suas propriedades. "Em geral, acho que subestimamos o poder dos algoritmos e superestimamos nossa própria capacidade de encontrá-los", disse Williams. Se SETH é verdadeiro ou falso, o que importa é a capacidade de usá-lo como uma ferramenta para mapear o que Williams chama de topografia da complexidade computacional.Indyk concorda. Embora ele não tenha provado que a distância de edição é impossível de ser resolvida com mais eficiência, ele provou que esse problema tratável teoricamente está fundamentalmente ligado à dureza intrínseca dos problemas NP-completos. O trabalho é como descobrir um misterioso istmo conectando duas massas de terra que antes eram consideradas oceanos separadas. Por que essa conexão estranha existe? O que isso nos diz sobre os contornos do litoral matemático que define os problemas difíceis?"P versus NP e SETH estão perguntando sobre a mesma coisa, apenas quantificando de forma diferente", disse Aaronson. “Queremos saber, quanto melhor podemos fazer do que procurar cegamente as respostas para esses problemas computacionais muito difíceis? Existe um caminho mais rápido e mais inteligente para a verdade matemática, ou não? Quão perto podemos chegar? ”A diferença entre resolver os mistérios de SETH e aqueles de P versus NP, acrescenta Aaronson, pode ser significativa em grau, mas não em espécie. “Quais seriam as implicações de descobrir uma civilização extraterrestre contra mil?” Ele meditou. "Uma descoberta é mais impressionante do que a outra, mas ambas são monumentais."
tradução de: A New Map Traces the Limits of Computation
Comentários
Postar um comentário