Teoria della complessità computazionale: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica Etichette: Modifica da mobile Modifica da web per mobile |
|||
Riga 1:
In [[informatica]], 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. I problemi sono classificati in differenti ''[[classe di complessità|classi di complessità]]'', in base all'efficienza del migliore [[algoritmo]] noto in grado di risolvere
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. 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.
| |||