La complessità,
un concetto alla volta.

Una dispensa da esplorare: scopri che cosa significa una classe, riconosci i suoi problemi e allenati sulle tracce d'esame.

Inizia da NP Apri una traccia

Una prima bussola

PRisolvere in tempo polinomiale
⊆\subseteqNPVerificare un sì in tempo polinomiale
⊆\subseteqPSPACERisolvere con spazio polinomiale

P⊆NP⊆PSPACE\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}} \subseteq \htmlData{term=PSPACE}{\mathrm{PSPACE}}. Le inclusioni sono note; non sappiamo se sono strette.

Un percorso per il ripasso

Scegli da dove iniziare
01

Capisci le classi

Dalla verifica di un certificato ai limiti di tempo e spazio.

Il punto di partenza02

Collega i concetti

Problemi concreti, riduzioni e teoremi: dai un significato alla mappa.

Dalla teoria agli esempi03

Mettiti alla prova

Rispondi alle domande d’esame e usa le spiegazioni per il ripasso.

Preparati all’esame