Eu, como muitas pessoas, sou um usuário perspicaz de software matemático como Mathematica e Maple. No entanto, fico cada vez mais frustrado com os muitos casos em que esse software simplesmente fornece a resposta errada sem aviso prévio. Isso pode ocorrer ao executar todos os tipos de operações, de somas simples a otimização, entre muitos outros exemplos.
Fiquei me perguntando o que poderia ser feito sobre esse grave problema. O que é necessário é uma maneira de permitir ao usuário verificar a exatidão de uma resposta que é dada, para que eles tenham alguma confiança no que estão sendo informados. Se você quiser obter uma solução de um colega de matemática, ele / ela pode simplesmente sentar e mostrar o trabalho deles. No entanto, isso não é viável para um computador na maioria dos casos. O computador poderia lhe dar uma testemunha simples e facilmente verificável da exatidão de sua resposta? A verificação pode ter que ser feita por computador, mas espero que a verificação do algoritmo de verificação seja muito mais fácil do que a verificação do algoritmo para produzir a testemunha em primeiro lugar. Quando isso seria possível e como exatamente isso poderia ser formalizado
Então, em resumo, minha pergunta é a seguinte.
Poderia ser possível, pelo menos em teoria, que o software matemático forneça uma pequena prova verificável junto com a resposta que você pediu?
Um caso trivial em que podemos fazer isso imediatamente é a fatoração de números inteiros, é claro, ou muitos dos problemas clássicos de NP-completos (por exemplo, circuito Hamiltoniano etc.).
fonte
Respostas:
O conceito de "testemunhas" ou "provas verificáveis" não é totalmente novo: como mencionado nos comentários, procure o conceito de "certificado". Três exemplos vieram à mente, há mais (nos comentários e em outros lugares):
Kurt Mehlhorn descreveu em 1999 um problema semelhante nos algoritmos de geometria computacional (por exemplo, pequenos erros nas coordenadas podem gerar grandes erros nos resultados de algum algoritmo), resolvidos de maneira semelhante na biblioteca Leda , insistindo que cada algoritmo produz um "certificado" da sua resposta, além da própria resposta.
Demaine, Lopez-Ortiz e Munro em 2000 usaram os conceitos de certificados (eles os chamam de "provas") para mostrar limites inferiores adaptativos no cálculo da união e interseção (e diferença, mas essa é trivial) dos conjuntos classificados. Não exclua seu trabalho porque eles não usaram certificados para se proteger contra erros de computação: eles mostraram que, embora o certificado possa ser linear no tamanho da instância, na pior das hipóteses, geralmente é mais curto e, portanto, pode ser "verificado" "em tempo sublinear (acesso aleatório à entrada como uma matriz classificada ou uma Árvore B) e, em particular, em tempo menor que o necessário para calcular esse certificado.
Eu tenho usado o conceito de certificados em vários outros problemas desde que Ian Munro apresentou sua implementação no Alenex 2001 , e em particular para permutações (desculpas pelo plugue descarado, outro está chegando), onde o certificado é mais curto, na melhor das hipóteses. do que no pior caso ou na média, que gera uma estrutura de dados compactada para permutações. Aqui, novamente, verificar o certificado (ou seja, o pedido) leva no tempo mais linear, menos do que calculá-lo (ou seja, classificar).
O conceito nem sempre é útil para a verificação de erros: há problemas em que a verificação do certificado leva tanto tempo quanto produzi-lo (ou simplesmente produzir o resultado). Dois exemplos vêm à mente, um trivial e outro complicado, Blum e Kannan (mencionados nos comentários) dão a outros.
A biblioteca Leda é o esforço mais geral (que eu conheço) para tornar os algoritmos deterministas de produção de certificados a norma na prática. O artigo de Blum e Kannan é o melhor esforço que vi para torná-lo a norma em teoria, mas eles mostram os limites dessa abordagem.
Espero que ajude...
fonte