Teoria della complessità computazionale: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica Etichette: Modifica da mobile Modifica da web per mobile |
||
Riga 1:
Ma con quale coraggio sei entrato in questa pagina? Vabbè.. In [[informatica]], la '''teoria della complessità computazionale''' è una branca della [[teoria della computabilità]] che studia le [[risorsa informatica|risorse]] minime necessarie (principalmente tempo di calcolo e [[memoria informatica|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 ''[[classe di complessità|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; ciò pone in 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.
| |||