Essa pode ser uma pergunta básica, mas eu tenho lido e tentado entender artigos sobre assuntos como computação de equilíbrio de Nash e teste de degeneração linear e não tenho certeza de como os números reais são especificados como entrada. Por exemplo, quando se afirma que o LDT possui certos limites inferiores polinomiais, como os números reais são especificados quando são tratados como entrada?
cc.complexity-theory
computability
na.numerical-analysis
computing-over-reals
computable-analysis
Philip White
fonte
fonte
Respostas:
Discordo da sua resposta aceita por Kaveh. Para programação linear e equilíbrios de Nash, o ponto flutuante pode ser aceitável. Mas os números de ponto flutuante e a geometria computacional se misturam muito mal: o erro de arredondamento invalida as suposições combinatórias dos algoritmos, freqüentemente causando o colapso. Mais especificamente, muitos algoritmos de geometria computacional dependem de testes primitivos que verificam se um determinado valor é positivo, negativo ou zero. Se esse valor estiver muito próximo de zero e o arredondamento do ponto flutuante fizer com que ele tenha o sinal errado, coisas ruins podem acontecer.
Em vez disso, as entradas geralmente são assumidas como tendo coordenadas inteiras e os resultados intermediários geralmente são representados exatamente, como números racionais com precisão suficientemente alta para evitar transbordamentos ou como números algébricos. Aproximações de ponto flutuante a esses números podem ser usadas para acelerar os cálculos, mas apenas em situações em que é possível garantir que os números estejam suficientemente longe de zero para que os testes de sinais dêem as respostas corretas.
Na maioria dos trabalhos de algoritmos teóricos em geometria computacional, essa questão é contornada assumindo que as entradas são números reais exatos e que as primitivas são testes exatos dos sinais de raízes de polinômios de baixo grau nos valores de entrada. Mas se você estiver implementando algoritmos geométricos, tudo isso se tornará muito importante.
fonte
Você também pode dar uma olhada na palestra de Andrej Bauer sobre O papel do domínio de intervalo na aritmética real exata moderna , que examina algumas das diferentes abordagens para especificar a computação sobre os números reais, tanto na teoria quanto na prática.
fonte
Esta não é uma resposta direta à sua pergunta, é mais uma resposta a Rafael . Recentemente, houve bastante trabalho especificando cálculos de números reais usando coindução. Aqui estão alguns artigos sobre o assunto.
Coindução para computação com números reais exatos , Ulrich Berger e Tie Hou: TEORIA DOS SISTEMAS DE COMPUTAÇÃO Volume 43, Números 3-4, 394-409, DOI: 10.1007 / s00224-007-9017-6
Raciocínio formal coindutivo na aritmética real exata , Milad Niqui, Métodos Lógicos em Ciência da Computação, 4 (3: 6): 1–40, 2008.
Cálculo em forma coindutiva de Dusko Pavlovic e Martin Escardo, LICS 1998.
Eles dificilmente cobrem todo o espectro da computação em número real, mas estão sendo feitos progressos para reduzir vários problemas.
fonte
A complexidade computacional das computações sobre números reais é considerada por Blum, Cucker, Shub e Smale . Aqui está uma descrição parcial do livro:
Você pode encontrar uma resenha deste livro no ACM SIGACT News .
fonte
Editado / corrigido com base nos comentários
Quando os autores falam sobre entradas de números reais na programação linear, computação de equilíbrio de Nash, ... na maioria dos trabalhos (trabalhos que não tratam de computação / complexidade sobre números reais), eles realmente não significam números reais. São números racionais e números que surgem deles devido a suas manipulações (números algébricos). Então você pode pensar nelas como representadas por seqüências finitas.
Por outro lado, se o artigo trata de computabilidade e complexidade na análise , eles não estão usando o modelo usual de computação e existem vários modelos incompatíveis de computação / complexidade sobre números reais.
Se o documento não especificar um modelo de computação sobre números reais, você pode assumir com segurança que é o primeiro caso, ou seja, são apenas números racionais.
Geometria Computacional é diferente. Na maioria dos trabalhos em CG, se os autores não especificarem qual é o modelo que, com relação a ele, a correção e a complexidade de um algoritmo está sendo discutida, pode-se supor que seja o modelo BSS (também conhecido como RAM real).
O modelo não é realista e, portanto, a implementação não é direta. (Essa é uma das razões pelas quais algumas pessoas na CCA preferem modelos teóricos de Ko-Friedman / TTE / Domain , mas o problema com esses modelos é que eles não são tão rápidos quanto a computação em ponto flutuante na prática.) o algoritmo no modelo BSS não transfere necessariamente para a correção do algoritmo implementado.
O livro de Weihrauch contém uma comparação entre diferentes modelos (Seção 9.8). São apenas três páginas e vale a pena ler.
(Também existe uma terceira maneira, que pode ser mais adequada para CG, você pode dar uma olhada neste artigo:
onde EGC é computação geométrica exata .)
fonte
Eles não são e não podem, em geral. Só podemos tratar um número contável de entradas (e saídas e funções) com nossos modelos de computação. Em particular, qualquer entrada deve ser finita, mas nem todos os números reais têm representações finitas.
Suponho que você poderia assumir algum tipo de oráculo que produz o próximo dígito de um certo número real mediante solicitação (sth como um fluxo). Caso contrário, você terá que conviver com aproximações (arbitrariamente precisas).
fonte