Problemi intrattabili e quantum computing Il problema del commesso viaggiatore • Noto anche come Travelling Salesman Problem (TSP) • Il commesso viaggiatore deve visitare n città in automobile • Se viaggiasse per una distanza totale maggiore di k il viaggio non gli converrebbe più (per il costo della benzina) • Ogni città è collegata direttamente a tutte le altre • Esiste un percorso di lunghezza < k che visita una sola volta tutte le città ? Bari Ancona ? Como Domodossola (Un) algoritmo 1. disponi le città in una permutazione qualunque…ABCD 2. somma le distanze tra A e B, tra B e C, tra C e D; se la somma è < k stampa il percorso e termina con successo 3. se non ci sono altre permutazioni termina con fallimento, altrimenti scegline un’altra e riparti dal passo 2 Complessità di TSP • Nel caso peggiore, dobbiamo esaminare tutte le permutazioni possibili • Date n città, le possibili permutazioni sono n! • TSP è O(n!) • Se n = 30, n! = 2,61032 • Un computer capace di esaminare 1000 miliardi di percorsi al secondo, lanciato all’istante presunto del big bang, dovrebbe lavorare ancora per 8000 miliardi di anni Problemi (in)trattabili • Si dicono intrattabili problemi i cui algoritmi richiedono una quantità irragionevolmente alta di risorse • Attualmente la distinzione tra problemi trattabili e non si basa sulla polinomialità • Problemi in O(nk) sono considerati trattabili Problemi di complessità polinomiale • Sono considerati trattabili in base all’esperienza • O(n10300) non è affatto ragionevole • Fino ad oggi, però, per tutti i problemi con complessità polinomiale si è sempre trovato un algoritmo al più O(n4) • Se un giorno si dovesse scoprire un problema polinomiale il cui migliore algoritmo è O(n10300), allora l’equivalenza polinomiale ~ trattabile andrebbe rivista La classe P • Contiene i problemi per i quali esiste un algortimo di complessità polinomiale • Il TSP ha un algoritmo O(n!) • Perché TSP sia dimostrabilmente in P, dobbiamo esibire un algoritmo O(nk) che lo risolva • Finora non è stato trovato niente del genere Verifica di possibile soluzione TSP • Dato un possibile percorso, verificare che soddisfa le condizioni del TSP < k? Verifica di possibile soluzione TSP • Avviene in tempo lineare rispetto al numero di città: O(n) • Se potessimo controllare tutti i percorsi possibili contemporaneamente, avremmo un algoritmo O(n) per TSP Macchina di Turing < < < < < < < < < < < < k? k? k? k? k? k? k? k? k? k? k? k? < < < < < < < < < < < < k? k? k? k? k? k? k? k? k? k? k? k? Macchina di Turing non deterministica • È tale una MT la cui tavola può comprendere più di una quintupla in corrispondenza di una certa configurazione • Una MTN (MT non deterministica), in corrispondenza di certi input, riesce a produrre più di una singola sequenza di calcolo < < < < < < < < < < < < k? k? k? k? k? k? k? k? k? k? k? k? < < < < < < < < < < < < k? k? k? k? k? k? k? k? k? k? k? k? < < < < < < < < < < < < k? k? k? k? k? k? k? k? k? k? k? k? < < < < < < < < < < < < k? k? k? k? k? k? k? k? k? k? k? k? La classe NP • TSP è O(n) per una MT non deterministica, perché viene effettuata contemporaneamente la verifica (di complessità lineare) per ogni possibile percorso • TSP è dunque nella classe NP dei problemi nondeterministico-polinomiali • P NP, perché ovviamente se una MT risolve un problema in tempo polinomiale, anche una MTN è in grado di farlo P = NP ? • Clay Mathematics Institute One Bow Street Cambridge, Massachusetts 02138 USA http://www.claymath.org/millennium/ • Offerti $1000000 per chi lo dimostra o dimostra il contrario • Per dimostrare che P NP, ossia P NP, occorre dimostrare che esiste un problema in NP per il quale non esiste un algoritmo polinomiale La collocazione di TSP • TSP è sicuramente in NP perché una MTN lo risolve in tempo polinomiale • Attualmente, il migliore algoritmo per TSP è O(n22n) • Non è stato dimostrato che non si possa migliorare • Né è stato dimostrato che sicuramente esiste un algoritmo polinomiale Problemi di decisione • TSP è un problema di decisione • “Date queste città collegate in questo modo, esiste un percorso....?” • Sì / No Riduzione polinomiale • Siano dati un problema di decisione p e un input d • Sia R un algoritmo che, dati p e d in input, restituisce un altro problema p’ e un altro input d’ tali che p’(d’ ) = sì se e solo se p(d) = sì • Se R ha complessità polinomiale, si dice che p è polinomialmente riducibile a p’ Problemi NP-completi • Un problema NP si dice NP-completo quando tutti i problemi NP sono polinomialmente riducibili ad esso • È stato dimostrato che TSP lo è • I problemi NP-completi sono particolarmente interessanti perché se un giorno si trova un algoritmo polinomiale che ne risolve uno, allora avremo dimostrato che P = NP Realizzazione di una MTN • Una possibile strada da seguire per realizzare fisicamente una macchina che esegua calcoli in parallelo è lo sfruttamento dei fenomeni di tipo quantistico • Quantum computing Sovrapposizione • Se un’entità quantistica può trovarsi in due stati, oppure assumere due valori diversi, si trova in uno stato di sovrapposizione delle due situazioni, con un coefficiente di probabilità per ciascuna | = |0 + |1 ||2+ ||2 = 1 Interferenza • Un’entità quantistica può trovarsi in più di uno stato • Se vogliamo conoscere lo stato in cui si trova, dobbiamo effettuare una misura • Il tentativo stesso di misura interferisce con l’entità e determina un particolare valore che prima era solo una tra tante possibilità Correlazione • Nota anche come entanglement • Porta a un paradosso in cui sembra violato il principio di località di Einstein, secondo cui se A e B sono separati da una distanza superiore a ct non possono influenzarsi in alcun modo • La misura di una grandezza quantistica influenza istantaneamente a distanza un’altra grandezza quantistica correlata 0 1 01 Computer classici vs quantistici 0 1 1 2n registri per le 2n configurazioni 1 registro per le 2n configurazioni
Scarica
