Função desprezível

Em matemática, uma função desprezível é uma função $\mu :\mathbb{N}\to ℝ$ de modo que para cada inteiro positivo c existe um inteiro N_c tal que para todo x > N_c,

$|\mu (x)|<\frac{1}{x^c}.$

Da mesma forma, também podemos usar a seguinte definição: uma função $\mu :\mathbb{N}\to ℝ$ é desprezível , se para cada polinômio positivo poly(·) existe um número inteiro N_poly > 0 tal que para todo x > N_poly

$|\mu (x)|<\frac{1}{\mathrm{poly}(x)}.$

História

O conceito de desprezibilidade pode encontrar sua origem em modelos sólidos de análise. Embora os conceitos de "continuidade" e " infinitesimal" tenham se tornado importantes na matemática durante a época de Newton e Leibniz (1680), eles não estavam bem definidos até o final da década de 1810. A primeira definição razoavelmente rigorosa de continuidade na análise matemática deveu-se a Bernard Bolzano, que escreveu em 1817 a definição moderna de continuidade. Posteriormente, Cauchy, Weierstrass e Heine também definiram da seguinte forma (com todos os números no domínio dos números reais $ℝ$):

( Função contínua ) Uma função $f:ℝ\to ℝ$ é contínua em $x=x_0$ se para cada $\epsilon >0$, existe um número positivo $\delta >0$ de tal modo que $|x-x_0|<\delta$ implica $|f(x)-f(x_0)|<\epsilon .$

Esta definição clássica de continuidade pode ser transformada na definição de desprezibilidade em algumas etapas, alterando os parâmetros usados ​​na definição. Primeiro, no caso $x_0=\mathrm{\infty }$ com $f(x_0)=0$, devemos definir o conceito de "função infinitesimal":

( Infinitesimal ) Uma função contínua $\mu :ℝ\to ℝ$ é infinitesimal (como $x$ vai para o infinito) se para cada $\epsilon >0$ existe $N_{\epsilon }$ tal que para todos $x>N_{\epsilon }$

$|\mu (x)|<\epsilon .$

Em seguida, substituímos $\epsilon >0$ pelas funções $1/x^c$ onde $c>0$ ou pela $1/\mathrm{poly}(x)$ onde $\mathrm{poly}(x)$ é um polinômio positivo. Isso leva às definições de funções desprezíveis fornecidas no início deste artigo. Desde que as constantes $\epsilon >0$ possam ser expressas como $1/\mathrm{poly}(x)$ com um polinômio constante, isso mostra que as funções desprezíveis são um subconjunto das funções infinitesimais.

Uso em criptografia

Na criptografia moderna baseada em complexidade , um esquema de segurança é comprovadamente seguro se a probabilidade de falha de segurança (por exemplo, inverter uma função unilateral, distinguir bits pseudoaleatórios criptograficamente fortes de bits verdadeiramente aleatórios) é desprezível em termos da entrada $x$ = comprimento da chave criptográfica $n$. Daí vem a definição no topo da página porque o comprimento da chave $n$ deve ser um número natural.

No entanto, a noção geral de desprezibilidade não exige que o parâmetro de entrada $x$ seja o comprimento da chave $n$. De fato, $x$ pode ser qualquer sistema métrico predeterminado e a análise matemática correspondente ilustraria alguns comportamentos analíticos ocultos do sistema.

A formulação recíproca de polinomial é usada pela mesma razão que a delimitação computacional é definida como tempo de execução polinomial: ela tem propriedades de fechamento matemáticas que a tornam tratável no ambiente assintótico (consulte propriedades de fechamento). Por exemplo, se um ataque conseguir violar uma condição de segurança apenas com probabilidade desprezível e o ataque for repetido um número polinomial de vezes, a probabilidade de sucesso do ataque geral ainda permanece insignificante.

Na prática, pode se querer ter funções mais concretas limitando a probabilidade de sucesso do adversário e escolher o parâmetro de segurança grande o suficiente para que essa probabilidade seja menor do que algum limite, digamos 2⁻¹²⁸.

Propriedades de fechamento

Uma das razões pelas quais funções desprezíveis são usadas nos fundamentos da criptografia de complexidade teórica é que elas obedecem propriedades de fechamento. Especificamente,

1. Se $f,g:\mathbb{N}\to ℝ$ são desprezíveis, então a função $x\mapsto f(x)+g(x)$ é desprezível.
2. Se $f:\mathbb{N}\to ℝ$ é desprezível e $p$ é qualquer polinômio real, então a função $x\mapsto p(x)\cdot f(x)$ é desprezível.

Por outro lado, se $f:\mathbb{N}\to ℝ$ não é desprezível, então também não o é $x\mapsto f(x)/p(x)$ para qualquer polinômio real $p$.

Exemplos

• $n\mapsto x^{-n}$ é desprezível para qualquer $x\ge 2$.
• $f(n)=3^{-\sqrt{n}}$ é desprezível.
• $f(n)=n^{-\log n}$ é desprezível.
• $f(n)=(\log n{)}^{-\log n}$ é desprezível.
• $f(n)=2^{-c\log n}$ não é desprezível, para $c$ positivo.

Ver também

• Números fora do padrão
• Cálculo não padronizado

Referências

• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar periódico