Funksioni i papërfillshëm

Në matematikë, një funksion i papërfillshëm është një funksion  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 ,



Njëvlershëm, ne mund të përdorim edhe përkufizimin e mëposhtëm. Një funksion  ë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



 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  është i vazhdueshëm në  nëse për çdo , ekziston një numër pozitiv  sikurse  nënkupton 

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  me , ne duhet të përcaktojmë konceptin e " funksionit pambarimisht të vogël ":

 ( Infinitezimal ) Një funksion i vazhdueshëm  është pambarimisht i vogël (kur  shkon në pafundësi) nëse për çdo  ekziston  e tillë që për të gjithë 
  [ citim i nevojshëm ]

Më pas, zëvendësojmë  nga funksionet  ku  ose nga  ku  ë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  mund të shprehen si  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  = gjatësia e çelësit kriptografik  .

Megjithatë, nocioni i përgjithshëm i papërfillshmërisë nuk kërkon që inputi  është gjatësia kryesore  . Me të vërtetë,  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,

 Nëse  janë të papërfillshme, pastaj funksioni  është i papërfillshëm.
 Nëse  është i papërfillshëm dhe  është çdo polinom i real, atëherë funksioni  është i papërfillshëm.

Në të kundërt, nëse  nuk është e papërfillshëm, atëherë as nuk është  për çdo polinom real  .

 Shembuj 

  është i papërfillshëm për çdo  .
  është i papërfillshëm.
  është i papërfillshëm.
  është i papërfillshëm.
  nuk është i papërfillshëm, për vlera të  pozitive .

Supozoni , marrim limitin kur  :

Të papërfillshme :


  për 
  për 


Jo të papërfillshme:



Kategoria:Analizë matematike
Kategoria:Faqe me përkthime të pashqyrtuara