Quais são as razões pelas quais os pesquisadores em geometria computacional preferem o modelo BSS / RAM real?

fundo

A computação sobre números reais é mais complicada do que a computação sobre números naturais, já que números reais são objetos infinitos e existem incontáveis ​​números reais; portanto, números reais não podem ser representados fielmente por seqüências finitas sobre um alfabeto finito.

Ao contrário da computabilidade clássica sobre cadeias finitas, onde diferentes modelos de computação, como: cálculo lambda, máquinas de Turing, funções recursivas, ... acabam sendo equivalentes (pelo menos para a computação sobre funções em cadeias), existem vários modelos propostos para computação sobre números reais que não são compatíveis. Por exemplo, no modelo TTE (veja também [Wei00]), que é o mais próximo do modelo clássico de máquina de Turing, os números reais são representados usando fitas de entrada infinitas (como os oráculos de Turing) e não é possível decidir a comparação e relações de igualdade entre dois números reais dados (em quantidade finita de tempo). Por outro lado, nos modelos BBS / RAM real, que são semelhantes ao modelo de máquina RAM, temos variáveis ​​que podem armazenar números reais arbitrários, e comparação e igualdade estão entre as operações atômicas do modelo. Por essa e outras razões semelhantes, muitos especialistas dizem que os modelos BSS / RAM real não são realistas (não podem ser implementados, pelo menos não nos computadores digitais atuais) e preferem o TTE ou outros modelos equivalentes ao TTE, como o modelo teórico de domínio eficaz, Modelo de Ko-Friedman, etc.

Se entendi corretamente , o modelo padrão de computação usado na Geometria Computacional é o modelo BSS (também conhecido como RAM real , consulte [BCSS98]).

Por outro lado, parece-me que na implementação dos algoritmos em Geometria Computacional (por exemplo, LEDA ), estamos lidando apenas com números algébricos e sem objetos ou cálculos infinitos de tipo superior envolvidos (isso está correto?). Portanto, parece-me (provavelmente ingênuo) que também se pode usar o modelo clássico de computação sobre cadeias finitas para lidar com esses números e usar o modelo usual de computação (que também é usado para a implementação dos algoritmos) para discutir a correção e a complexidade. de algoritmos.

Questões:

Quais são as razões pelas quais os pesquisadores em Geometria Computacional preferem usar o modelo BSS / RAM real? (explica a geometria computacional específica para usar o modelo BSS / RAM real)

Quais são os problemas com a ideia (provavelmente ingênua) que mencionei no parágrafo anterior? (usando o modelo clássico de computação e restringindo as entradas a números algébricos em Geometria Computacional)

Termo aditivo:

Há também a complexidade da questão dos algoritmos, é muito fácil decidir o seguinte problema no modelo BSS / RAM real:

$S$$T$
$\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$

Embora nenhum algoritmo eficiente de RAM inteira seja conhecido para resolvê-lo. Agradecimentos a JeffE pelo exemplo.

Referências:

1. Lenore Blum, Felipe Cucker, Michael Shub e Stephen Smale, "Complexidade e computação real", 1998
2. Klaus Weihrauch, " Análise Computável, Uma Introdução ", 2000

Antes de tudo, os geômetros computacionais não pensam nisso como o modelo BSS. O verdadeiro modelo de RAM foi definido por Michael Shamos em sua tese de doutorado em 1978 ( Geometria Computacional ), que sem dúvida lançou o campo. Franco Preparata revisou e estendeu a tese de Shamos no primeiro livro de geometria computacional, publicado em 1985. A RAM real também é equivalente ( exceto a uniformidade; veja a resposta de Pascal! ) Ao modelo de árvore de computação algébrica definido por Ben-Or em 1983. Blum , Os esforços de Shub e Smale foram publicados em 1989, bem depois que a RAM real foi estabelecida e foram quase completamente ignorados pela comunidade de geometria computacional.

A maioria dos resultados (clássicos) em geometria computacional está fortemente ligada a questões na geometria combinatória , para as quais suposições sobre coordenadas sendo integrais ou algébricas são (na melhor das hipóteses) distrações irrelevantes. Falando como nativo, parece completamente natural considerar pontos arbitrários , linhas, círculos e similares como objetos de primeira classe ao provar coisas sobre eles e, portanto, igualmente natural ao projetar e analisar algoritmos para computar com eles.

$p$$q$$q$$r$$q,r,s$$qr$$st$? Cada uma dessas primitivas é implementada avaliando o sinal de um polinômio de baixo grau nas coordenadas de entrada. (Portanto, esses algoritmos podem ser descritos no modelo de árvore de decisão algébrica mais fraca .) Se as coordenadas de entrada forem inteiras, essas primitivas poderão ser avaliadas exatamente com apenas um aumento constante de precisão e, portanto, os tempos de execução na RAM real e no RAM inteira são os mesmos.

Por razões semelhantes, quando a maioria das pessoas pensa em algoritmos de classificação, elas não se importam com o que estão classificando, desde que os dados venham de um universo totalmente ordenado e quaisquer dois valores possam ser comparados em tempo constante.

Assim, a comunidade desenvolveu uma separação de preocupações entre o design de algoritmos geométricos "reais" e sua implementação prática; daí o desenvolvimento de pacotes como LEDA e CGAL. Mesmo para as pessoas que trabalham com computação exata, há uma distinção entre o algoritmo real , que usa aritmética real exata como parte do modelo subjacente, e a implementação , que é forçada pelas limitações irrelevantes dos dispositivos físicos de computação a usar a computação discreta.

$\times$

Existem alguns algoritmos geométricos que realmente dependem muito do modelo de árvore de computação algébrica e, portanto, não podem ser implementados de maneira exata e eficiente em computadores físicos. Um bom exemplo são os caminhos de link mínimo em polígonos simples, que podem ser calculados em tempo linear em uma RAM real, mas requerem um número quadrático de bits no pior caso para representar exatamente. Outro bom exemplo são os cortes hierárquicos de Chazelle , que são usados ​​nos algoritmos mais eficientes conhecidos na pesquisa por faixa simplex. Essas estacas usam uma hierarquia de conjuntos de triângulos, em que os vértices dos triângulos em cada nível são pontos de interseção de linhas pelas arestas dos triângulos nos níveis anteriores. Assim, mesmo que as coordenadas de entrada sejam números inteiros, as coordenadas de vértice para esses triângulos são números algébricos de grau ilimitado; no entanto, os algoritmos para construir e usar aparas assumem que as coordenadas podem ser manipuladas exatamente em tempo constante.

Portanto, minha resposta curta e pessoal é a seguinte: TTE, teoria de domínio, Ko-Friedman e outros modelos de computação em número real "realistas", todos tratam de questões que a comunidade de geometria computacional, no geral, simplesmente não se importa .

Não é bem verdade que o modelo real de RAM / BSS é equivalente ao modelo de árvore de computação algébrica. O último é mais poderoso porque uma árvore de profundidade polinomial pode ser de tamanho exponencial. Isso dá muito espaço para codificar informações não uniformes. Por exemplo, Meyer auf der Heide mostrou que as árvores de decisão algébricas (mesmo lineares) podem resolver problemas difíceis com eficiência, como a soma de subconjuntos, mas isso é (conjecturalmente) impossível no modelo real de RAM / BSS.

Aqui está um comentário sobre a excelente resposta de Jeff:

Noções de condição, aproximação e arredondamento foram propostas para abordar a lacuna de complexidade (combinatória vs. contínua) dos algoritmos de programação linear. A condição de uma instância de problema estima o efeito de pequenas perturbações da entrada na precisão da saída. A noção de condição foi introduzida pela primeira vez por Alan Turing. Jim Renegar introduziu a noção de condição de um programa linear.

L. BLUM, Computação sobre os reais: Onde Turing Atende Newton, , convocatórias da AMS, Volume 51, Número 9, (2004), 1024-1034

A. TURING, Erros de arredondamento nos processos matriciais, Quart. J. Mech. Appl. Matemática. 1 (1948), 287-308

J. RENEGAR, Incorporando números de condição na teoria da complexidade da programação linear, SIAM J. Optim. 5 (1995), 506-524

F. CUCKER e J. PEÑA, um algoritmo primal-duplo para resolver sistemas cônicos poliédricos com uma máquina de precisão finita, SIAM Journal on Optimization 12 (2002), 522–554.