Como julgar a definição de complexidade computacional de reais é natural ou adequada?

Como sabemos, a definição de complexidade computacional do algoritmo é quase sem controvérsia, mas a definição de complexidade computacional de reais ou os modelos de computação sobre reais não é nesse caso. Conhecemos o modelo e o modelo de Blum e Smales no livro Análise Computável. E, aparentemente, o modelo em Análise Computável é consistente com o modelo clássico, mas a definição de complexidade computacional de reais não pode ser transplantada para o modelo clássico.

E como transplantar a definição de complexidade computacional de reais para o modelo clássico?

cc.complexity-theory reference-request computability computing-over-reals computable-analysis XL _At_Here_There
fonte

Para sua primeira pergunta, "natural" é uma noção muito subjetiva e, dependendo da pessoa que você perguntar, uma ou outra definição será considerada a mais natural. Quanto a "adequado", depende: o modelo BSS parece adequado para geometria computacional ou geometria algébrica computacional, e o modelo em Análise Computável é mais adequado para ... análise computável! Eu não entendo a segunda pergunta.

de Bruno

@Bruno, obrigado pelo seu comentário, acho que o modelo em Análise Computável, e não sei como aplicar a definição de complexidade computacional à computação de número real sobre modelo clássico como Turing Machine, já que a complexidade computacional de número real sobre modelo na Análise computável depende da representação, ou seja, da entrada para o cálculo.

XL _At_Here_There

Você parece pensar que existe uma noção de complexidade para o cálculo de números reais, independente da representação dos reais. O que te faz pensar isso? Este também não é o caso da complexidade clássica. Não importa se você tem uma fita ou uma máquina de RAM, é importante saber se você representa gráficos por listas adjancency ou 01-matrizes, etc.

Andrej Bauer

Mas não é verdade que a complexidade não dependa da representação. Ao mudar para uma representação estúpida, você sempre pode arruinar a complexidade de um algoritmo. A pergunta a ser feita é: "O que é uma boa representação da entrada?" Para problemas discretos, é muito mais fácil responder do que para números reais, porque se tem uma boa noção do que significa "não desperdiçar bits".

Andrej Bauer

o modelo BSS parece adequado para geometria computacional - Veja minha resposta a uma pergunta relacionada . O modelo de RAM real usado pelos geômetros computacionais antecede Blum, Shub e Smale em quase uma década.

Jeffε

Respostas:

Não sei exatamente qual é a pergunta aqui, mas posso tentar dizer um pouco para limpar possíveis mal-entendidos.

$f : \mathbb{R} \to \mathbb{R}$ $\sqrt{2}$ $f$

$f : A \to B$ $A$ $(a, f(a))$ $f$

$\mathbb{R}$ $\mathbb{R}$ $\mathbb{R}$

$+$ $\times$ $-$ $/$ $|{-}|$
$x$ $k \in \mathbb{N}$ $p, q$ $|x - p/q| \leq 2^{-k}$
$x$ $y$ $x < y$
$(x_n)_n$ $|x_{n+1} - x_n| \leq 2^{-n}$ $\lim_n x_n$

Existem velhos teoremas (consulte a introdução deste artigo para referências) que explicam por que essas condições são as corretas. Esses teoremas também mostram que quaisquer duas representações de reais são computáveis isomórficas, ou seja, podemos traduzir entre elas com programas. Isso define alguns critérios de correção que descartam idéias defeituosas.

Por exemplo, ouço pessoas dizerem coisas como "números racionais podem ser representados por informações finitas, então vamos usá-los para números racionais, e os números irracionais terão que ser representados por informações infinitas". Esse tipo de coisa não funciona porque quebra a quarta condição acima (considere um limite de números irracionais - como você dirá que está convergindo para um racional?).

Outro exemplo que as condições acima eliminam é o modelo de Blum-Shub-Smale, porque nele você não pode calcular limites de sequências. É melhor dizer que o modelo BSS funciona em um subcampo ordenado discreto de reais (gerado por quaisquer parâmetros que estejam presentes), não nos reais.

Entre as representações corretas dos reais, algumas são mais eficientes que outras, embora este seja um tópico um pouco difícil de discutir, porque números reais são objetos infinitos. Matthias Schröder apontou que, para uma teoria razoável da complexidade, é preciso prestar atenção às propriedades topológicas da representação.

Por fim, como devemos medir a complexidade de um mapa , assumindo que temos uma boa representação de ? Como é representado por uma função, ou um fluxo infinito de informações, ou algo assim, devemos usar uma das noções de complexidade do tipo superior . Qual deles provavelmente depende da representação que você está usando. $f : \mathbb{R} \to \mathbb{R}$ $\mathbb{R}$ $x \in \mathbb{R}$

O modelo BSS também é um modelo razoável de complexidade de circuitos no qual contamos operações aritméticas. É bom lembrar que esse modelo não é sobre números reais, mas sobre outra coisa.

Andrej Bauer
fonte

Muito obrigado pela sua resposta e por tantas referências. Sinto-me desconfortável com algumas noções de complexidade computacional, deixe-me ler a referência e pensar por um tempo e dar um exemplo, se encontrar uma adequada para explicar por que estou tão desconfortável (isso parece engraçado, mas minha experiência me diz se me sinto desconfortável, deve haver algo singular)

XL _At_Here_There

Na minha experiência, sentir-se desconfortável com novos conhecimentos é um bom sinal e, geralmente, é um pré-requisito para a iluminação.

András Salamon

Outro modelo possível de explorar é o modelo de RAM viável. Este é um modelo de RAM real modificado para computação Real, RAM viável ou um modelo de RAM modificado que usa operações aritméticas discretas e com valores reais. Esse modelo permite operações reais e discretas, e o modelo de Turing é intercambiável com ele. O modelo de RAM viável possui precisão definida com incerteza, o que significa que permite comparações de números reais apenas até uma incerteza variável 1 / (k + 1). Isso permite cálculos aproximados. Além disso, como Vasco Brattkaa e Peter Hertlingb afirmam em Máquinas de acesso aleatório real viáveis - os modelos de Turing e de RAMs reais viáveis estão relacionados. Todas as funções computáveis em uma máquina de Turing no tempo $<_{k}$ $O(t)$ são computáveis em uma RAM no tempo e, no caso inverso, há alguma sobrecarga para a máquina de Turing que calcula a função (se a RAM real calcula a função em a TM calcula a função em . Como as considerações topológicas apontadas são úteis, não se sabe se existe algum contexto topológico desenvolvido para esse modelo de computação que permita computações reais - que tem incerteza em precisão. $O(t)$ $O(t)$ $O(t^{2}log(t)log(log(t)))$

user3483902
fonte

Você poderia dar alguma referência para o modelo de RAM viável?

XL _At_Here_There

Veja acima na área, "... esta referência indica ..." tem um link para o artigo.

user3483902

Obrigado por apontar para o trabalho da Brattka & Hertling, eu já ia mencioná-lo. Gostaria apenas de salientar que o modelo de RAM viável não inclui funções de ordem superior; em particular, ele não pode computar o limite de uma sequência Cauchy (rápida); portanto, não consideraria isso como a implementação "dos reais" com precisão. Ele pode calcular um limite "no nível superior", por assim dizer (veja a parte do artigo em que eles falam sobre aproximações racionais de funções).

Andrej Bauer