Classe di complessità: differenze tra le versioni

Versione delle 14:23, 12 mag 2021

Versione delle 14:02, 14 feb 2022

Riga 1:

Nella [[teoria della complessità computazionale]], una '''classe di complessità''' è un [[insieme]] di [[Problema computazionale|problemi]] di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma:

:l'insieme di problemi che, se esiste la soluzione, possono essere risolti da una [[macchina astratta]] M usando <math>O(f(n))</math> della risorsa R, con <math>n</math> dimensione dell'input

Riga 187:

== Voci correlate ==

* [[GlossarioLista delle classi di complessità]]

* [[Teoria della calcolabilità]]

* [[Teoria della complessità computazionale]]