Un problema è considerato intrinsecamente difficile se la sua soluzione richiede risorse significative, indipendentemente dall' algoritmo utilizzato. La teoria formalizza questa intuizione, introducendo modelli matematici di calcolo per studiare questi problemi e quantificando la quantità di risorse necessarie per risolverli, come il tempo e la memorizzazione. Vengono utilizzate anche altre misure di complessità, come la quantità di comunicazione (utilizzata nella complessità della comunicazione), il numero di cancelli in un circuito (utilizzato nella complessità del circuito) e il numero di processori (utilizzati nel calcolo in parallelo). Uno dei ruoli della teoria della complessità computazionale è quello di determinare i limiti pratici su ciò che il computer può e non può fare.
Quale misura di un problema computazionale definisce in senso lato la difficoltà intrinseca della soluzione?
se la sua soluzione richiede risorse significative se la sua soluzione richiede risorse significative