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 metodo viene utilizzato per valutare o quantificare intuitivamente la quantità di risorse necessarie per risolvere un problema computazionale?
modelli matematici di calcolo modelli matematici di calcolo modelli matematici di calcolo