Na matemática, uma função negligenciável é uma função tal que, para cada inteiro positivo c, existe um inteiro Nc tal que, para todo n > Nc,
De forma equivalente, a seguinte definição pode ser utilizada. Uma função é negligenciável se, para cada polinômio positivo poli(·), existe um inteiro Npoli > 0 tal que, para todo n > Npoli
História O conceito de negligenciabilidade pode ter suas origens traçadas de volta a modelos sólidos de análise. Embora os conceitos de "continuidade" e "infinitésimo" tenham se tornado importantes na matemática durante a época de Newton e Leibniz (década de 1680), eles não foram 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. Mais tarde, Cauchy, Weierstrass e Heine também definiram o conceito como se segue (com todos os números no domínio dos números reais ):
(Função contínua) Uma função é contínua em se, para cada , existe um número positivo tal que implica
Esta definição clássica de continuidade pode ser transformada na definição de negligenciabilidade em poucos passos, alterando os parâmetros utilizados na definição. Primeiro, no caso de com , devemos definir o conceito de "função infinitesimal":
(Infinitésimo) Uma função contínua é infinitesimal (quando tende ao infinito) se, para cada , existe tal que, para todo
Em seguida, no contexto discreto em que a entrada é um número natural , substituímos pelas funções onde , ou por onde é um polinômio positivo. Isso leva às definições de funções negligenciáveis fornecidas no topo deste artigo. Como as constantes podem ser expressas como com um polinômio constante, isso mostra que as funções infinitesimais (restritas a ) são um superconjunto das funções negligenciáveis.
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 unidirecional, distinguir bits pseudoaleatórios criptograficamente fortes de bits genuinamente aleatórios) for negligenciável em termos do parâmetro de segurança ou comprimento da chave criptográfica . Daí decorre a definição no topo da página, pois o parâmetro de entrada deve ser um número natural.
No entanto, a noção geral de negligenciabilidade não exige que o parâmetro de entrada seja estritamente o comprimento da chave. De fato, pode ser qualquer métrica discreta de sistema predeterminada, e a análise matemática correspondente ilustraria alguns comportamentos analíticos ocultos do sistema.
A formulação do inverso do polinômio é usada pelo mesmo motivo que a limitação computacional é definida como tempo de execução polinomial: ela possui propriedades de fechamento matemático que a tornam tratável no cenário assintótico (veja #Propriedades de fechamento). Por exemplo, se um ataque consegue violar uma condição de segurança apenas com probabilidade negligenciável, e o ataque é repetido um número polinomial de vezes, a probabilidade de sucesso do ataque geral ainda permanece negligenciável.
Na prática, pode-se desejar 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 um determinado limite, por exemplo, 2−128.
Propriedades de fechamento
Uma das razões pelas quais as funções negligenciáveis são usadas nos fundamentos da criptografia baseada na teoria da complexidade computacional é que elas obedecem a propriedades de fechamento. Especificamente,
Se são negligenciáveis, então a função é negligenciável. Se é negligenciável e é qualquer polinômio real, então a função é negligenciável.
Conversamente, se não é negligenciável, então também não é, para qualquer polinômio real .
Exemplos
é negligenciável para qualquer constante : Passo: Esta é uma função de decaimento exponencial onde é uma constante maior ou igual a 2. Quando , muito rapidamente, tornando-a negligenciável. é negligenciável: Passo: Esta função possui decaimento exponencial com base 3, mas o expoente cresce mais lentamente que (apenas a uma taxa de ). Quando , , então ela ainda é negligenciável, mas decai mais lentamente do que . é negligenciável: Passo: Neste caso, representa um decaimento superpolinomial, com o expoente crescendo negativamente devido ao . Como a taxa de decaimento aumenta com , a função vai para 0 mais rápido do que funções polinomiais como para qualquer constante , tornando-a negligenciável. é negligenciável: Passo: Esta função decai conforme o logaritmo de é elevado a um expoente negativo , o que leva a uma aproximação rápida de 0 quando . O decaimento aqui é mais rápido do que as taxas logarítmicas inversas ou polinomiais, tornando-a negligenciável. não é negligenciável, para um positivo: Passo: Podemos reescrever isto como , que é um decaimento polinomial em vez de um exponencial. Como é positivo, quando , mas não decai tão rapidamente quanto as funções exponenciais verdadeiras em relação a , tornando-a não negligenciável.
Assumindo que e fixada uma constante real , calculamos o limite quando :
Negligenciáveis:
Passo: Esta função decai exponencialmente com a base elevada à potência de . Quando , rapidamente, tornando-a negligenciável. para : Passo: Podemos simplificar como , que decai mais rápido do que qualquer polinômio. Quando , a função se aproxima de zero e é considerada negligenciável para qualquer e . para : Passo: O decaimento é determinado pela base elevada à potência de . Como cresce com , esta função se aproxima de zero mais rápido do que o decaimento polinomial, tornando-a negligenciável. : Passo: Aqui, decai exponencialmente com uma base de elevada a . Quando , rapidamente, por isso é considerada negligenciável. : Passo: Com uma base exponencial e expoente , esta função se aproximaria do zero de forma extremamente rápida, sugerindo negligenciabilidade.
Não negligenciável:
Passo: Como quando , esta função decai muito lentamente, falhando em se aproximar de zero rápido o suficiente para ser considerada negligenciável.
Ver também Álgebra de Colombeau Cálculo não padrão Conjunto negligenciável Números não padrão Teorema de Gromov sobre grupos de crescimento polinomial
Referências
Categoria:Análise matemática Categoria:Tipos de funções