În exemplul de mai sus, vedem că, cu 100 {\displaystyle 100}
de pietre, există 2 100 {\displaystyle 2^{100}}
moduri de a împărți setul de pietre. Cu n {\displaystyle n} 
roci, există 2 n {\displaystyle 2^{n}}
combinații. Funcția f ( n ) = 2 n {\displaystyle f(n)=2^{n}}
este o funcție exponențială. Este importantă pentru NP deoarece modelează cel mai rău caz numărul de calcule necesare pentru a rezolva o problemă și, prin urmare, cel mai rău caz de timp necesar.
Și până acum, pentru problemele dificile, soluțiile au necesitat de ordinul a 2 n {\displaystyle 2^{n}} calcule. Pentru orice problemă specifică, oamenii au găsit modalități de a reduce numărul de calcule necesare. Cineva ar putea găsi o modalitate de a face doar 1% din numărul de calcule în cel mai rău caz și să economisească o mulțime de calcule, dar asta înseamnă tot 0,01 × ( 2 n ) {\displaystyle 0,01\ ori (2^{n})} 
calcule. Și fiecare piatră în plus încă dublează numărul de calcule necesare pentru a rezolva problema. Există perspective care pot produce metode pentru a efectua chiar mai puține calcule, producând variații ale modelului: de exemplu, 2 n / n 3 {\displaystyle 2^{n}/n^{3}}. 
. Dar funcția exponențială continuă să domine pe măsură ce n {\displaystyle n} crește.
Luați în considerare problema programării examenelor (descrisă mai sus). Dar să presupunem, în continuare, că există 15000 de studenți. Există un program de calculator care preia orarele tuturor celor 15000 de studenți. Acesta rulează într-o oră și produce un program de examene astfel încât toți studenții să-și poată face examenele într-o săptămână. Acesta respectă o mulțime de reguli (nu se pot da examene consecutive, nu se pot da mai mult de 2 examene în orice perioadă de 28 de ore, ...) pentru a limita stresul din săptămâna examenelor. Programul rulează timp de o oră în pauza de la jumătatea semestrului și toată lumea își cunoaște programul de examene cu suficient timp pentru a se pregăti.
În anul următor, însă, sunt cu 10 studenți în plus. Dacă același program rulează pe același calculator, atunci acea oră se va transforma în 2 10 {\displaystyle 2^{10}} 
ore, deoarece fiecare elev în plus dublează calculele. Asta înseamnă 6 {\displaystyle 6} 
săptămâni! Dacă ar fi fost 20 de studenți în plus, atunci
2 20 {\displaystyle 2^{20}}
ore = 1048576 {\displaystyle 1048576}
ore ~ 43691 {\displaystyle 43691} 
zile ~ 113 {\displaystyle 113} 
ani
Astfel, pentru 15000 {\displaystyle 15000} de 
elevi, este nevoie de o oră. Pentru 15020 {\displaystyle 15020} 
studenți, este nevoie de 113 {\displaystyle 113} ani.
După cum puteți vedea, funcțiile exponențiale cresc foarte repede. Majoritatea matematicienilor consideră că cele mai dificile probleme NP necesită un timp exponențial pentru a fi rezolvate.
