Classe di complessità: differenze tra le versioni

Versione delle 14:02, 14 feb 2022

Versione attuale delle 21:35, 15 feb 2025

(2 versioni intermedie di un altro utente 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:

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 190 ⟶ 191:

* [[Teoria della calcolabilità]]

* [[Teoria della complessità computazionale]]

== Collegamenti esterni ==

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

{{Classi di complessità}}