Efficienza (informatica): differenze tra le versioni

I problemi NP (in particolari NP-Completi) non sono ancora stati risolti in tempo polinomiale e non si conosce se è possibile farlo<ref>[https://www.claymath.org/millennium/P_vs_NP/ Problema del millennio P=NP?] {{webarchive|url=https://web.archive.org/web/20131014194456/http://www.claymath.org/millennium/P_vs_NP/ |data=14 ottobre 2013 }}</ref>. L'utilizzo di algoritmi sempre più vicini a una soluzione non esponenziale sono fondamentali per quei software che utilizzano problemi così complessi. Sono molto più frequenti di quanto si pensi, per esempio il [[problema dello zaino]] è alla base dei nostri [[navigatore satellitare|navigatori satellitari]].