#MT06 – Breve guida ai problemi complessi
Tradotto dall’originale di Kevin Hartnett – pubblicato il 16 lug 2018
Quanto è fondamentalmente difficile un problema? Questo è il compito fondamentale degli informatici che sperano di classificare i problemi in quelle che vengono chiamate classi di complessità. Si tratta di gruppi che contengono tutti i problemi di calcolo che richiedono meno di una quantità fissa di risorse computazionali, come il tempo o la memoria. Prendiamo un esempio con un numero grande come 123.456.789.001. Ci si potrebbe chiedere: questo numero è primo, cioè divisibile solo per 1 e per se stesso? Gli informatici possono risolvere questo problema utilizzando algoritmi veloci, che non si bloccano quando il numero diventa arbitrariamente grande. Nel nostro caso, 123.456.789.001 non è un numero primo. Allora potremmo chiederci: quali sono i suoi fattori primi? In questo caso non esiste un algoritmo così veloce, a meno che non si utilizzi un computer quantistico. Per questo gli informatici ritengono che i due problemi appartengano a classi di complessità diverse.
Esistono molte classi di complessità diverse, anche se nella maggior parte dei casi i ricercatori non sono riusciti a dimostrare che una classe è categoricamente distinta dalle altre. Dimostrare questo tipo di distinzioni categoriali è uno dei problemi aperti più difficili e importanti del settore. Ecco perché il nuovo risultato di cui ho scritto il mese scorso su Quanta è stato considerato un grande affare: in un articolo pubblicato alla fine di maggio, due scienziati informatici hanno dimostrato (con un’avvertenza) che le due classi di complessità che rappresentano i computer quantistici e classici sono davvero diverse.
Le differenze tra le classi di complessità possono essere sottili o nette, e mantenere le classi in ordine è una sfida. Per questo motivo, Quanta ha preparato questo manuale su sette delle classi di complessità più importanti. Che non possiate mai più confondere BPP e BQP.
P
Sta per: Tempo polinomiale (Polynomial time)
Versione breve: Tutti i problemi che sono facili da risolvere per un computer classico (cioè non quantistico).
Versione estesa: Gli algoritmi in P devono fermarsi e dare la risposta giusta in un tempo massimo di nc, dove n è la lunghezza dell’input e c è una costante.
Problemi tipici:
Un numero è primo?
Qual è il percorso più breve tra due punti?
Cosa vogliono sapere i ricercatori: P è la stessa cosa di NP? Se così fosse, la scienza informatica verrebbe sconvolta e la maggior parte della crittografia sarebbe inefficace da un giorno all’altro. (Quasi nessuno pensa che sia così).
NP
Sta per: Tempo polinomiale non deterministico (Nondeterministic Polynomial time)
Versione breve: Tutti i problemi che possono essere verificati rapidamente da un computer classico una volta data la soluzione.
Versione estesa: Un problema è in NP se, data una risposta affermativa, esiste una breve dimostrazione che stabilisce che la risposta è corretta. Se l’input è una stringa, X, e si deve decidere se la risposta è “sì”, una prova breve sarebbe un’altra stringa, Y, che può essere usata per verificare in tempo polinomiale che la risposta è effettivamente “sì”. (Y viene talvolta definito “testimone breve”: tutti i problemi in NP hanno “testimoni brevi” che consentono di verificarli rapidamente).
Problemi tipici:
Il problema delle comunità. Immaginate un grafo con spigoli e nodi – per esempio, un grafo in cui i nodi sono persone su Facebook e due nodi sono collegati da uno spigolo se sono “amici”. Una comunità è un sottoinsieme di questo grafo in cui tutte le persone sono amiche di tutte le altre. Ci si può chiedere se un grafo di questo tipo sia in grado di soddisfare le seguenti domande: Esiste una comunità di 20 persone? 50 persone? 100? Trovare una tale comunità è un problema “NP-completo”, cioè ha la più alta complessità di tutti i problemi in NP. Ma se si dà una risposta potenziale – un sottoinsieme di 50 nodi che possono o meno formare una comunità – è facile verificarlo.
Il problema del commesso viaggiatore. Dato un elenco di città con le distanze tra ogni coppia di città, esiste un modo per attraversare tutte le città in meno di un certo numero di chilometri? Ad esempio, un commesso viaggiatore può attraversare tutte le capitali degli Stati Uniti in meno di 11.000 miglia?
Cosa vogliono sapere i ricercatori: P = NP? Gli scienziati informatici non sono affatto vicini alla soluzione di questo problema.
PH
Sta per: Gerarchia polinomiale (Polynomial Hierarchy)
Versione breve: PH è una generalizzazione di NP – contiene tutti i problemi che si ottengono se si parte da un problema in NP e si aggiungono ulteriori livelli di complessità.
Versione estesa: PH contiene problemi con un certo numero di “quantificatori” alternati che rendono i problemi più complessi. Ecco un esempio di problema con quantificatori alternati: Dato X, esiste Y tale che per ogni Z esiste W tale che R si verifichi? Più quantificatori contiene un problema, più è complesso e più si trova in alto nella gerarchia dei polinomi.
Problema tipico:
Determinare se esiste una comunità di dimensione 50 ma nessuna di dimensione 51.
Cosa vogliono sapere i ricercatori: Gli informatici non sono riusciti a dimostrare che PH è diverso da P. Questo problema è equivalente al problema P contro NP perché se (inaspettatamente) P = NP, allora tutto PH collassa a P (cioè P = PH).
PSPACE
Sta per: Spazio polinomiale (Polynomial Space)
Versione breve: PSPACE contiene tutti i problemi che possono essere risolti con una quantità ragionevole di memoria.
Versione estesa: In PSPACE non ci si preoccupa del tempo, ma solo della quantità di memoria necessaria per eseguire un algoritmo. Gli informatici hanno dimostrato che PSPACE contiene PH, che contiene NP, che contiene P.
Problema tipico:
Ogni problema in P, NP e PH è in PSPACE.
Cosa vogliono sapere i ricercatori: PSPACE è diverso da P?
BQP
Sta per: Tempo polinomiale quantistico a errore limitato (Bounded-error Quantum Polynomial time)
Versione breve: Tutti i problemi che sono facili da risolvere per un computer quantistico.
Versione estesa: Tutti i problemi che possono essere risolti in tempo polinomiale da un computer quantistico.
Problema tipico:
Identificare i fattori primi di un numero intero.
Cosa vogliono sapere i ricercatori: Gli informatici hanno dimostrato che BQP è contenuto in PSPACE e che BQP contiene P. Non sanno se BQP è in NP, ma ritengono che le due classi siano incomparabili: Ci sono problemi che sono in NP e non in BQP e viceversa.
EXPTIME
Sta per: Tempo esponenziale (Exponential Time)
Versione breve: Tutti i problemi che possono essere risolti in un tempo esponenziale da un computer classico.
Versione estesa: EXP contiene tutte le classi precedenti: P, NP, PH, PSPACE e BQP. I ricercatori hanno dimostrato che è diversa da P – hanno trovato problemi in EXP che non sono presenti in P.
Problema tipico:
Le generalizzazioni di giochi come gli scacchi e la dama sono in EXP. Se una scacchiera può essere di qualsiasi dimensione, diventa un problema in EXP determinare quale giocatore è in vantaggio in una determinata posizione sulla scacchiera.
Cosa vogliono sapere i ricercatori: Gli informatici vorrebbero poter dimostrare che PSPACE non contiene EXP. Ritengono che ci siano problemi che si trovano in EXP che non sono in PSPACE, perché a volte in EXP è necessaria molta memoria per risolvere i problemi. Gli scienziati informatici sanno come separare EXP e P.
BPP
Sta per: Tempo polinomiale probabilistico a errore limitato (Bounded-error Probabilistic Polynomial time)
Versione breve: Problemi che possono essere risolti rapidamente da algoritmi che includono un elemento di casualità.
Versione estesa: BPP è esattamente la stessa cosa di P, ma con la differenza che l’algoritmo può includere fasi in cui il suo processo decisionale è randomizzato. Gli algoritmi in BPP sono tenuti solo a dare la risposta giusta con una probabilità prossima a 1.
Problema tipico:
Si hanno a disposizione due formule diverse che producono ciascuna un polinomio con molte variabili. Le formule calcolano esattamente lo stesso polinomio? Questo è il cosiddetto problema della verifica dell’identità dei polinomi.
Cosa vogliono sapere i ricercatori: Gli informatici vorrebbero sapere se BPP = P. Se ciò fosse vero, significherebbe che ogni algoritmo randomizzato può essere de-randomizzato. I ricercatori ritengono che sia così – che esista un algoritmo deterministico efficiente per ogni problema per il quale esiste un algoritmo randomizzato efficiente – ma non sono riusciti a dimostrarlo.
Articolo originale: Read More
