Algoritmi - Problemi polinomiali

Ciao a tutti,
sto studiando la complessita degli algoritmi e mi sono sorti dei dubbi sui problemi polinomiali.

Su wikipedia c'è scritto:

La classe di problemi NP comprende tutti quei problemi decisionali che, per verificare la correttezza di una data soluzione, impiegano un tempo polinomiale. La classe NP prende il suo nome dall'abbreviazione di Nondeterministic Polynomial Time.

Ok, ma cos'è un "tempo polinomiale" ?

Andando un po' per intuito credo che un problema polinomiale abbia una complessità non solo dipendente da una sola variabile n ma da più variabili.

ad esempio O((n^2)*k) potrebbe essere un problema polinomiale in quanto non dipende solo da n ma anche da k

Ho detto una fesseria, oppure ho capito?
Grazie a tutti!

un tempo polinomiale è una funzione t = P(n), dove t è il tempo e P(n) è un polinomio nella variabile n (nel nostro caso corrisponde alla dimensione dell'input).

Un polinomio, nel caso non lo sapessi, è un'espressione nella forma:

A0 + A1 n + A2 n^2 + A3 n^3 + ...... + Ak n^k
Dove A0, A1, A2, .... Ak sono k+1 costanti reali (anche lo zero è una costante).
Quindi sono polinomi:

3
4 + 5n
n^2
n + 4n^3
ecc...

Se il tempo di esecuzione di un algoritmo può essere espresso in forma di polinomio, allora quell'algoritmo ha una complessità polinomiale.
Alcuni esempi di espressioni NON-polinomiali (trascendenti):
2^n (esponenziale)
log(n) (logaritmica)
tan(n) (trigonometrica)
n * log(n) ( trascendente generica )

tempo polinomiale vuol dire che il tempo per effettuare una determinata operazione dipende dal numero di elementi sui cui opera secondo una legge polinomiale (ovvero un polinomio di grado superiore al primo).

un esempio è il bubble sort: O(n^2) è polinomiale