Teoria della complessità computazionale
branca della teoria della computabilità / Da Wikipedia, l'enciclopedia encyclopedia
Caro Wikiwand AI, Facciamo breve rispondendo semplicemente a queste domande chiave:
Puoi elencare i principali fatti e statistiche su Teoria della complessità computazionale?
Riassumi questo articolo per un bambino di 10 anni
La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce dunque alle risorse di calcolo richieste. I problemi sono classificati in differenti classi di complessità, in base all'efficienza del migliore algoritmo noto in grado di risolvere quello specifico problema.
Una distinzione informale, ma di grande rilievo, è quella posta tra i cosiddetti problemi facili, di cui si conoscono algoritmi di risoluzione efficienti, e difficili, di cui gli unici algoritmi noti non sono efficienti. Ad esempio la maggior parte della crittografia moderna si fonda sull'esistenza di problemi ritenuti difficili; ha enorme rilevanza lo studio di tali problemi, poiché, qualora si dimostrasse l'esistenza di un algoritmo efficiente per un problema ritenuto difficile, i sistemi crittografici basati su di esso non sarebbero più sicuri.