Funksioni i papërfillshëm

Në matematikë, një funksion i papërfillshëm është një funksion $\mu :\mathbb{N}\to ℝ$ i tillë që për çdo numër të plotë pozitiv c ekziston një numër i plotë N _c i tillë që për të gjithë x > N _c ,

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

Njëvlershëm, ne mund të përdorim edhe përkufizimin e mëposhtëm. Një funksion $\mu :\mathbb{N}\to ℝ$ është i papërfillshëm, nëse për çdo polinom pozitiv poly (·) ekziston një numër i plotë N _poli > 0 e tillë që për të gjitha x > N _poli

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

Historia

Koncepti i papërfillshmërisë mund të gjejë gjurmën e tij në modelet e shëndosha të analizës. Megjithëse konceptet e " vazhdimësisë " dhe " infitezimalitetit " u bënë të rëndësishme në matematikë gjatë kohës së Njutonit dhe Leibnizit (1680), ato nuk ishin të mirëpërcaktuara deri në fund të viteve 1810. Përkufizimi i parë mjaft rigoroz i vazhdimësisë në analizën matematikore ishte për shkak të Bernard Bolzanos, i cili shkroi në 1817 përkufizimin modern të vazhdimësisë. Më vonë Cauchy, Vajershtrasi dhe Heine përcaktuan gjithashtu si më poshtë (me të gjithë numrat në domenin e numrave realë $ℝ$ ):

( Funksioni i vazhdueshëm ) Një funksion $f:ℝ\to ℝ$ është i vazhdueshëm në $x=x_0$ nëse për çdo $\epsilon >0$, ekziston një numër pozitiv $\delta >0$ sikurse $|x-x_0|<\delta$ nënkupton $|f(x)-f(x_0)|<\epsilon .$

Ky përkufizim klasik i vazhdimësisë mund të shndërrohet në përkufizimin e papërfillshmërisë në disa hapa duke ndryshuar parametrat e përdorur në përkufizim. Së pari, në rastin $x_0=\mathrm{\infty }$ me $f(x_0)=0$, ne duhet të përcaktojmë konceptin e " funksionit pambarimisht të vogël ":

( Infinitezimal ) Një funksion i vazhdueshëm $\mu :ℝ\to ℝ$ është pambarimisht i vogël (kur $x$ shkon në pafundësi) nëse për çdo $\epsilon >0$ ekziston $N_{\epsilon }$ e tillë që për të gjithë $x>N_{\epsilon }$

$|\mu (x)|<\epsilon .$ </link>

Më pas, zëvendësojmë $\epsilon >0$ nga funksionet $1/x^c$ ku $c>0$ ose nga $1/\mathrm{poly}(x)$ ku $\mathrm{poly}(x)$ është një polinom pozitiv. Kjo çon në përkufizimet e funksioneve të papërfillshme të dhëna në krye të këtij artikulli. Meqënëse konstantet $\epsilon >0$ mund të shprehen si $1/\mathrm{poly}(x)$ me një polinom konstant kjo tregon se funksionet e papërfillshme janë një nëngrup i funksioneve pambarimisht të vogla.

Përdorimi në kriptografi

Në kriptografinë moderne të bazuar në kompleksitet, një skemë sigurie është e provueshme dhe e sigurt nëse probabiliteti i dështimit të sigurisë (p.sh., përmbysja e një funksioni të njëanshëm, dallimi i biteve pseudorastësore të forta kriptografike nga bitet vërtet të rastit) është i papërfillshëm për sa i përket inputit $x$ = gjatësia e çelësit kriptografik $n$ .

Megjithatë, nocioni i përgjithshëm i papërfillshmërisë nuk kërkon që inputi $x$ është gjatësia kryesore $n$ . Me të vërtetë, $x$ mund të jetë çdo metrikë e paracaktuar e sistemit dhe analiza matematikore përkatëse do të ilustronte disa sjellje analitike të fshehura të sistemit.

Formulimi i ndërsjellë i polinomit përdoret për të njëjtën arsye që kufiri llogaritës përkufizohet si koha e ekzekutimit të polinomit: ai ka veti matematikore të mbylljes që e bëjnë atë të lëvizshëm në kushte asimptotike. Për shembull, nëse një sulm arrin të shkelë një kusht sigurie vetëm me probabilitet të papërfillshëm, dhe sulmi përsëritet një numër polinomi herë, probabiliteti i suksesit të sulmit të përgjithshëm mbetet ende i papërfillshëm.

Në praktikë, dikush mund të dëshirojë të ketë më shumë funksione konkrete që kufizojnë probabilitetin e suksesit të kundërshtarit dhe të zgjedhë parametrin e sigurisë mjaft të madhe që ky probabilitet të jetë më i vogël se një prag, le të themi 2 ^{− 128} .

Vetitë e mbylljes

Një nga arsyet që funksionet e papërfillshme përdoren në themelet e kriptografisë së teorisë së kompleksitetit të llogaritjes është sepse ato u binden vetive mbyllëse. Konkretisht,

1. Nëse $f,g:\mathbb{N}\to ℝ$ janë të papërfillshme, pastaj funksioni $x\mapsto f(x)+g(x)$ është i papërfillshëm.
2. Nëse $f:\mathbb{N}\to ℝ$ është i papërfillshëm dhe $p$ është çdo polinom i real, atëherë funksioni $x\mapsto p(x)\cdot f(x)$ është i papërfillshëm.

Në të kundërt, nëse $f:\mathbb{N}\to ℝ$ nuk është e papërfillshëm, atëherë as nuk është $x\mapsto f(x)/p(x)$ për çdo polinom real $p$ .

Shembuj

• $n\mapsto a^{-n}$ është i papërfillshëm për çdo $a\ge 2$ .
• $f(n)=3^{-\sqrt{n}}$ është i papërfillshëm.
• $f(n)=n^{-\log n}$ është i papërfillshëm.
• $f(n)=(\log n{)}^{-\log n}$ është i papërfillshëm.
• $f(n)=2^{-c\log n}$ nuk është i papërfillshëm, për vlera të $c$ pozitive .

Supozoni $n>0$, marrim limitin kur $n\to \mathrm{\infty }$ :

Të papërfillshme :

• $f(n)=1/x^{n/2}$
• $f(n)=1/x^{\log (n^k)}$ për $k\ge 1$
• $f(n)=1/x^{({\log n)}^k}$ për $k\ge 1$
• $f(n)=1/x^{\sqrt{n}}$

Jo të papërfillshme:

• $f(n)=\frac{1}{n^{\frac{1}{n}}}$
• $f(n)=\frac{1}{x^{n(\log n)}}$