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

Come si usa

  1. 1. Scegli un concetto.
  2. 2. Apri un esempio.
  3. 3. Prova una domanda.

I termini sottolineati offrono un aiuto al passaggio, al focus o al tocco.

Le risorse del calcolo

Classi di complessità

CalcolabilitàEsponenzialeSpazio pol.Gerarchia polinomialeTempo pol.Spazio logaritmico⊊NEXP ⊊ R: inclusione stretta ricavata dai risultati del corso⊊R ⊊ RE: inclusione stretta dimostrata⊊R ⊊ coRE: inclusione stretta dimostrata≠RE ≠ coRE (ricavata dalla validità del primo ordine)Lspazio log nNL= coNLP= Σ₀ᴾ = Δ₁ᴾNP ∩ coNPprove corte in entrambi i versiNP= Σ₁ᴾcoNP= Π₁ᴾDPNP ∧ coNPΔ2P= P^NPΣ2P= NP^NPΠ2P= coNP^NPΣiPpiani i ≥ 3ΠiPpiani i ≥ 3PH⋃ ΣᵢᴾPSPACE= NPSPACEEXPtempo 2^polyNEXPnondet. 2^polyRdecidibiliREsemidecidibilicoREcomplementi di RE
inclusione dimostrata, non si sa se stretta
inclusione stretta dimostrata
separazione dimostrata tra classi lontane
non si sa nemmeno se una contiene l'altra

Come si collegano due classi? →

Scegli una coppia e distingui inclusioni note, separazioni e questioni aperte.

Algoritmi quantistici →

Grover, Shor e quando conviene il calcolo quantistico, come nella Lezione 6.