Classe di complessità: differenze tra le versioni

Versione delle 14:23, 12 mag 2021

Versione attuale delle 21:35, 15 feb 2025

(3 versioni intermedie di 2 utenti non mostrate)

Riga 1:

[[File:Complexity subsets pspace.svg|miniatura|Rappresentazione delle varie classi di complessità|300x300px]]

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 84 ⟶ 85:

| colspan=1 |

{| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%"

| align="center" | [[PSPACE-Completocompleto|PSPACE-Completi]]

|}

|- align="center"

Riga 187 ⟶ 188:

== Voci correlate ==

* [[GlossarioLista delle classi di complessità]]

* [[Teoria della calcolabilità]]

* [[Teoria della complessità computazionale]]

== Collegamenti esterni ==

* {{FOLDOC|complexity class|complexity class}}

{{Classi di complessità}}