Aplicações de números adic no CS

11

Existem exemplos concretos (ou uma rica fonte de) de aplicação de números adic na ciência da computação? $p$

survey T ....
fonte

número p- adic / Wikipedia. usado na teoria dos números. de certa forma indireta, por exemplo, há algumas análises da conjectura de Collatz viateoria p- adica e Collatz é considerado por alguns como profundamente conectado à pesquisa de indecidibilidade do TCS.

vzn

13

De, Kurur, Saha e Saptharishi forneceram uma versão modular do algoritmo de multiplicação de números inteiros de Fürer em seu artigo Multiplicação rápida de números inteiros usando aritmética modular , na qual os números p-adic substituem os números complexos usados pela Fürer. Ambos os algoritmos fornecem a melhor complexidade de bits para multiplicação de números inteiros.

Yuval Filmus
fonte

Este é um bom exemplo.

T ....

10

O levantamento de Hensel está intimamente relacionado aos -adics: está basicamente obtendo uma aproximação cada vez melhor de um número adic, "melhor" no sentido de "mais próximo na avaliação adic. O levantamento de Hensel é usado em muitos algoritmos como fatorar polinômios ou fazer álgebra linear sobre (se bem me lembro, Dixon tem um artigo sobre este último). $p$ $p$ $p$ $\mathbb{Z}$

Joshua Grochow
fonte

Z_{p} [x]

$\Bbb Z_p[x]$

R [x]

$\Bbb R[x]$

11

Z_{p}

$\mathbb{Z}_p$

p

$p$

Q_{p} [x]

$\mathbb{Q}_p[x]$

R [x]

$\mathbb{R}[x]$

p

$p$

Z_{p} [x]

$\mathbb{Z}_p[x]$

Z [x]

$\mathbb{Z}[x]$

p

$p$

Q_{p} [x]

$\Bbb Q_p[x]$

R [x]

$\Bbb R[x]$

@JA: Eu não sei - se você encontrar um uso ou uma referência a um uso, informe-nos!

Joshua Grochow 26/10

6

Existem também alguns modelos computacionais:

Aqui está o primeiro artigo: Rusins Freivalds: autômatos ultramétricos e máquinas de Turing. Turing-100 2012: 98-112

Abuzer Yakaryilmaz
fonte

4

Aqui está uma boa pesquisa geral com uma breve visão geral de diversas aplicações de CS (recentes) para a teoria p- adica, p3

O que são números p-Adic? Para que são usados? / Rozikov

Aqui estão as áreas em que a dinâmica p-adic provou ser eficaz: ciência da computação (programas lineares), análises e simulações numéricas (números pseudo-aleatórios), distribuição uniforme de seqüências, criptografia (cifras de fluxo, funções T), combinatória (quadrados latinos) , teoria dos autômatos e linguagens formais, genética. A monografia [9] contém a pesquisa correspondente. Para resultados mais recentes, consulte artigos e referências recentes: [10, 14, 15, 28, 36, 37, 38, 48, 51]. Além disso, existem estudos em ciência da computação e criptografia que, juntamente com a física matemática, estimularam, em 1990, pesquisas intensivas em dinâmica p-adic, uma vez que se observou que as principais instruções de computador (e, portanto, programas compostos por essas instruções) podem ser consideradas transformações contínuas. para a métrica 2-adic, consulte [11, 12].

vzn
fonte

Interessante. onde em programas de linha reta é usado?

T ....

11

Também estes não parecem trabalho convencional.

T ....

Aplicações de números adic no CS

Respostas: