Complessità computazionale

Concetti di Informatica

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Classi di complessità

Classi di complessità

Un'animazione che mostra l'intero spazio della complessità dei problemi

Un'immagine che mostra lo spazio dei problemi P

Classe di complessità -->	P (Tempo polinomiale)
Significato	Si risolvono velocemente ed efficientemente
Esempio	Ordinare una lista
Analogia	"Archiviare documenti in ordine alfabetico"
Punto chiave	Sono "facili" in termini computazionali

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Un'immagine che mostra gli insiemi di problemi P e NP

Classe di complessità -->	NP (Tempo polinomiale non deterministico)
Significato	Soluzioni verificabili, difficile trovarne di nuove
Esempio	Verificare che un Sudoku sia corretto
Analogia	"Trovare un documento specifico con info mancanti"
Punto chiave	Verificare è "facile", trovare nuove soluzioni è difficile

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Un'immagine che mostra gli insiemi di problemi P, NP e NP-Complete

Classe di complessità -->	NP-Complete
Significato	I più difficili in NP. Speciali perché risolvono tutti i problemi NP
Esempio	Problema del commesso viaggiatore
Analogia	"Un puzzle complesso: facile verificare, difficile risolvere"
Punto chiave	Nessuna soluzione efficiente nota; se trovata, risolve tutti i problemi NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Un'immagine che mostra P, NP, NP-Complete e NP-Hard

Classe di complessità -->	NP-Hard
Significato	Difficili quanto NP-Complete o di più
Esempio	Pianificazione ottimale con dipendenze complesse, non verificabile
Analogia	"Trovare l'orario ottimale con molti vincoli, non verificabile rapidamente"
Punto chiave	Forse impraticabili da risolvere

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Un diagramma che pone la classica domanda di ricerca: P=NP?

Concetti di Informatica