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...
O problema da soma das raízes quadradas pergunta, dadas duas seqüências e de números inteiros positivos, se a soma menor ou igual a ou maior que a soma . O status de complexidade desse problema está aberto; veja este post para mais detalhes. Esse problema surge naturalmente na geometria...
Um dos Santo Graal do projeto de algoritmos é encontrar um algoritmo fortemente polinomial para programação linear, ou seja, um algoritmo cujo tempo de execução é limitado por um polinômio no número de variáveis e restrições e é independente do tamanho da representação dos parâmetros (assumindo...
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...
Suponha que recebamos vários polígonos simples disjuntos no plano e dois pontos e fora de cada polígono. O problema do caminho mais curto euclidiano é calcular o caminho mais curto euclidiano de a que não cruza o interior de nenhum polígono. Para concretude, vamos assumir que as coordenadas de e ,...
Atualmente, o cálculo de reais nas línguas mais populares ainda é feito através de operações de ponto flutuante. Por outro lado, teorias como a efetividade do tipo dois (ETT) e a teoria do domínio há muito prometem o cálculo exato dos reais. Claramente, o problema da precisão do ponto flutuante não...
Qual é a complexidade (na RAM inteira padrão) de calcular a transformada discreta padrão de Fourier de um vetor de números inteiros?nnn O algoritmo clássico para transformações rápidas de Fourier , atribuídas inadequadamente [1] a Cooley e Tukey, é geralmente descrito como sendo executado em tempo...
É possível testar algoritmicamente se um número computável é racional ou inteiro? Em outras palavras, seria possível para uma biblioteca que implementa números computáveis fornecer as funções isIntegerou isRational? Suponho que isso não seja possível e que isso esteja de alguma forma relacionado...
Uma pergunta recente discutiu o agora clássico algoritmo de programação dinâmica para TSP, devido independentemente a Bellman e Held-Karp . O algoritmo é universalmente relatado para ser executado no tempo O ( 2nn2)O(2nn2)O(2^n n^2) . No entanto, como um dos meus alunos apontou recentemente, esse...
Existe um teorema geral que declararia, com sanitização adequada, que os resultados mais conhecidos sobre o uso de números reais podem realmente ser usados quando se considera apenas reais computáveis? Ou existe uma caracterização adequada dos resultados que permaneçam válidos ao considerar...
Estou estudando recentemente o modelo de computação BSS (por exemplo, Complexidade e Computação Real; Blum, Cucker, Shub, Smale). Para os reais , é mostrado que, dado um sistema de polinômios f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] , a existência de zeros é N P R incompleta. No entanto, eu estou me...
Nas notas de aula de Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf , diz-se que não sabemos se o TSP euclidiano está em NP: A razão é que não sabemos como calcular raízes quadradas com eficiência. Por outro lado, há este artigo de Papadimitriou:...
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,...
Alguém pode me apontar a referência para a não definibilidade do módulo de continuidade funcional no PCF? \ newcommand {\ bool} {\ mathsf {bool}}\newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Andrej Bauer escreveu um post muito bom no blog explorando alguns dos problemas com mais...
Usando o modelo real-RAM / BSS, temos a classe NP , (onde um BSS é o modelo Blum-Shub-Smale de um computador com operações sobre reais). Temos NP problemas completos. Então, a questão é: existe um análogo da conjectura de Berman Hartman para a classe NP ? Obviamente, a questão colocada aqui depende...
Dado um número algébrico , estou interessado em encontrar uma aproximação de até uma determinada precisão, em que se refere à parte real do número complexo.αα\alphaR(eα)ℜ(eα)\Re(e^\alpha)R()ℜ()\Re() Formalmente, quero calcular um número racional rrr tal que