[Algoritmi] Chiarimenti sul concetto di complessità

[P40L01]

Dal libro "Algebraic Aspects of Cryptography" di Neal Koblitz riporto la seguente definizione

Sia $L_n(\gamma;c)=\mathcal{O}(e^{c((lnn)^{\gamma}(lnlnn)^{1-\gamma})))$. In particolare $L_n(1;c)=\mathcal{O](n^c)$ e $L_n(0;c)=\mathcal{O}((lnn)^c)$. Un algoritmo $L(\gamma)$ è un algoritmo che, applicato ad un intero $n$, ha running time stimato di tipo $L_n(\gamma;c)$ per qualche $c$. In particolare un algoritmo a tempo polinomiale è un algoritmo $L(0)$, mentre un algoritmo a tempo esponenziale è un algoritmo $L(1)$. Un algoritmo a tempo sub-esponenziale è un algoritmo $L(\gamma)$ per qualche $\gamma<1$.

Segue poi qualche rigo dopo la seguente osservazione

La terminologia $L(\gamma)$ non è appropriata per tutti gli algoritmi. Ad esempio, algoritmi con running time maggiore di quello esponenziale non possono essere classificati con la definizione precedente. [...] Alcuni preferiscono dare una definizione diversa di "tempo sub-esponenziale", usando questa classificazione per indicare un algoritmo con running time limitato da una funzione di tipo $e^{f(k)}$ con $k$ lunghezza dell'input e $f(k)=o(k)$ [...] per esempio un algoritmo che ha $e^{\frac{k}{lnlnk}}$ operazioni è sub-esponenziale secondo quest'ultima definizione ma non secondo la definizione precedente.

Il testo "Aritmetica, crittografia e codici" di W.M. Baldoni e C. Ciliberto leggo

[...] se abbiamo una funzione $f(n)\in \mathcal{O}(n^k)$ possiamo dire che $f(n)\in \mathcal{O}(a^n)$ qualunque sia l'intero positivo $k$ e qualunque sia il numero reale $a>1$. Su questa semplice osservazione sono basate le seguenti due definizioni che sono di fondamentale importanza nello studio degli algoritmi.
Definizione 1
Un algoritmo $A$ per eseguire un calcolo su numeri interi si dice di tempo polinomiale o semplicemente polinomiale se esiste un intero positivo $d$, detto ordine dell'algoritmo, tale che il numero di operazioni di bit necessarie per eseguire l'algoritmo su interi di lunghezza binaria al più $k$ è $\mathcal{O}(k^d)$.
Definizione 2
Un algoritmo si dice di tempo esponenziale, o semplicemente esponenziale, se il numero di operazioni bit necessarie per eseguire l'algoritmo su interi di lunghezza binaria al più $k$ è dello stesso ordine di $e^{ck}$ per una costante $c>0$.

e infine...
Un algoritmo non esponenziale si dice subesponenziale se il numero di operazioni bit necessarie per eseguire l'algoritmo su interi di lunghezza binaria al più $k$ è $\mathcal{O}(e^k)$ [...]

Non riesco a cogliere il nesso tra le definizioni fornite da entrambi i libri (ammesso che ci sia) e soprattutto non riesco a comprendere pienamente cos'è un algoritmo a tempo sub-esponenziale... Sono molto confuso, aiutatemi!!!

[P40L01]

Riporto una classificazione della complessità degli algoritmi estrapolata dal link seguente http://web.mit.edu/16.070/www/lecture/big_o.pdf

Here is a list of classes of functions that are commonly encountered when analyzing
algorithms. The slower growing functions are listed first. c is some arbitrary constant.
Notation------>name
$\mathcal{O}(1)$------>constant
$\mathcal{O}(\log n)$------>logarithmic
$\mathcal{O}((\log n)^c)$------>polylogarithmic
$\mathcal{O}(n)$---------------->linear
$\mathcal{O}(n^2)$---------->quadratic
$\mathcal{O}(n^c)$---------->polynomial
$\mathcal{O}(c^n)$-----------> exponential

Perché nel testo di Neal Koblitz gli algoritmi di tipo $L_n(0;c)=\mathcal{O}((\log n)^c)$ e $L_n(1;c)=\mathcal{O}(n^c)$ vengono rispettivamente classificati a tempo polinomiale e a tempo esponenziale mentre nella tabella appena riportata sono classificati come "polilogaritmico"/esponenziale???

[hamming_burst]

Ciao,
posso chiederti che tipo di corso stai facendo e quale cdl (matematica?)?

[P40L01]

Ciao! Sono uno studente di matematica che per pura curiosità (e un pò da "autodidatta") si è avvicinato al mondo della crittografia.
Da quel che ho letto in merito alla crittografia a chiave pubblica mi è parso di capire che la sicurezza di gran parte dei crittosistemi a chiave pubblica è legata ai problemi di fattorizzazione degli interi (IFP), del logaritmo discreto (DLP) e del logaritmo discreto su curve ellittiche (ECDPL); ho intuito inoltre che i crittosistemi basati su curve ellittiche sono quelli più sicuri in quanto per risolvere ECDLP esistono solo algoritmi con running time esponenziale (tranne nel caso delle curve ellittiche supersingolari, per le quali è possibile utilizzare metodi index-calculus a tempo sub-esponenziale).
Ciò che non riesco proprio a cogliere pienamente è proprio questa distinzione sul running time (tempo di esecuzione?) degli algoritmi, anche perché sfogliando questo o quell'altro testo mi sembra (da profano) di trovare ogni volta definizioni diverse.