[q. computing] problemi np-completi e ctc

[CioKKoBaMBuZzo]

sul numero di maggio di "le scienze" c'è un bellissimo articolo di aaronson scott sui limiti dei computer quantistici e amenità varie collegate.

tra queste amenità varie collegate c'è anche una considerazione che riguarda un collegamento tra problemi np-completi e viaggi nel tempo o curve chiuse di tipo tempo (a seconda di quanto si vuole essere altisonanti e incomprensibili)

il ragionamento dell'autore è questo:
se si assume come principio fisico "nessun algoritmo può trovare la soluzione di un problema np-completo in un tempo polinomiale", allora i viaggi nel tempo non sono possibili, perchè si potrebbe trovare la soluzione di un problema np-completo in un tempo esponenziale e mandarla indietro nel tempo all'inizio del calcolo, riuscendo così a risolvere il problema in un tempo polinomiale.

ora, io non ho certo la pretesa di sapere qualcosa su viaggi nel tempo o quantum computing, ma il ragionamento mi stona un po'...a me più che un "risolvere il problema in un tempo polinomiale" sembra una sorta di trucco per aggirare un limite fisico, un pò come sfuttare la curvatura per spostarsi più velocemente della luce.

qualche addetto ai lavori o persona informata dei fatti potrebbe far luce dicendo la sua?

edit: pensandoci la domanda non è strettamente collegata al quantum computing...

[D.O.S.]

?
io ho letto quell'articolo ma non mi sembra dica una cosa del genere.

[gabi.2437]

Beh è la stessa storia del paradosso del nonno... solo in versione np :D

[D.O.S.]

forse ho capito
l'autore faceva un ragionamento un pochino contorto , anziché partire da una teoria fisica per vedere le conseguenze sulle macchine che usano tali principi faceva l'opposto : assumeva come intrattabili i problemi NP-completi e si chiedeva se era possibile dedurre da ciò che i viaggi nel tempo ( le linee CTC ) potessero esistere.

è un approccio di metodo , una possibilità che però non si può applicare ...

edit - ha spiegato meglio nella conclusione facendo un paragone con il secondo principio della termodinamica : viene usato per studiare altri tipi di fenomeni .
lui pensava di fare lo stesso con la Np-completezza ,considerandola come un principio , ma è un approccio sbagliato : bisogna prima dimostrarlo .

[CioKKoBaMBuZzo]

Beh è la stessa storia del paradosso del nonno... solo in versione np :D
no nell'articolo dice che qualcuno (non ricordo chi) ha trovato un modo per portare l'informazione evitando il paradosso

edit - ha spiegato meglio nella conclusione facendo un paragone con il secondo principio della termodinamica : viene usato per studiare altri tipi di fenomeni .
lui pensava di fare lo stesso con la Np-completezza ,considerandola come un principio , ma è un approccio sbagliato : bisogna prima dimostrarlo .
ma il mio dubbio è diverso. mettiamo che sia già stato dimostrato: l'autore sostiene che i viaggi nel tempo non sono possibili perchè sfruttandoli si potrebbero risolvere i problemi np-completi in breve tempo. ma (come dicevo nel primo post) a me sembra un po' come la stora dei viaggi a velocità curvatura: aggirare un limite fisico senza superarlo. perchè il problema verrebbe comunque risolto in un tempo esponenziale, non polinomiale

edit: ecco, un altro esempio: faccio partire il calcolo e poi mi faccio un viaggetto a velocità relativistica. quando ritorno sulla terra per me sarà passato poco tempo, ma per il computer ne è passato abbastanza da trovare la soluzione (in tempo esponenziale) et volià, il mio sistema di riferimento è riuscito ad avere la soluzione di un problema np-completo in poco tempo

[CioKKoBaMBuZzo]

answers needed :O

[CioKKoBaMBuZzo]

io ci spero ancora eh :asd:

[:.Blizzard.:]

è l'ultimo capitolo che mi manca da studiare per l'esame di algoritmi 2 :asd:

[:.Blizzard.:]

ps mi dai qualche info sulla rivista? Non mi dispiacerebbe leggere qualche rivista mensile di tipo scientifico (studio informatica, ma cmq nn disprezzo conoscenze che vadano "oltre")

[CioKKoBaMBuZzo]

bhè la rivista è "le scienze", la più famosa anche perchè l'unica autorevole di un certo livello in italia :asd: è la versione italiana di scientific american
costa 3,9€

[Banus]

ora, io non ho certo la pretesa di sapere qualcosa su viaggi nel tempo o quantum computing, ma il ragionamento mi stona un po'...a me più che un "risolvere il problema in un tempo polinomiale" sembra una sorta di trucco per aggirare un limite fisico, un pò come sfuttare la curvatura per spostarsi più velocemente della luce.
Seguo il suo blog e ne aveva parlato mesi fa. Aveva anche detto che il suo articolo era stato pesantemente modificato prima della pubblicazione, e nel draft i ragionamenti non erano così contorti... quindi aveva ragione ad essere irritato (e magari la traduzione italiana ha ulteriormente peggiorato la qualità) :D

D.O.S. ha afferrato all'incirca il senso: l'impossibilità di risolvere "efficientemente" (con risorse non esponenziali) i problemi NP è preso come principio fisico, dal quale si traggono varie conseguenze.
Il discorso delle CTC non è particolarmente rilevante (probabilmente l'enfasi è stata aggiunta da Scienze per catturare l'interesse sui viaggi nel tempo), mentre è molto più rilevante un altro fatto. Un comportamento non lineare della fisica quantistica, cioè una trasformazione ("operatore unitario") applicata a una sovrapposizione di stati non è la sovrapposizione degli stati ottenuta applicando la trasformazione sui singoli stati, porta alla possibilità di risolvere problemi NP in tempo polinomiale con un computer quantistico, anche se si suppone P <> NP. Molte teorie di gravità quantistica ipotizzano deviazioni non lineari della fisica quantistica in regimi non esplorati dagli esperimenti, e questa considerazione può essere rilevante per valutarne le conseguenze.

edit: ecco, un altro esempio: faccio partire il calcolo e poi mi faccio un viaggetto a velocità relativistica. quando ritorno sulla terra per me sarà passato poco tempo, ma per il computer ne è passato abbastanza da trovare la soluzione (in tempo esponenziale) et volià, il mio sistema di riferimento è riuscito ad avere la soluzione di un problema np-completo in poco tempo
Per ottenere una compressione esponenziale, hai bisogno di una quantità di energia esponenziale nelle dimensioni del problema, e serve un tempo esponenziale per fornire alla navicella sufficiente combustibile per il viaggio (supponendo di avere strumenti di portata finita) :p

lui pensava di fare lo stesso con la Np-completezza ,considerandola come un principio , ma è un approccio sbagliato : bisogna prima dimostrarlo .
In realtà come ho detto sopra l'assunzione di Scott non è P<>NP, che dipende dal un particolare modello di computazione (macchina di Turing deterministica), ma in generale l'impossibilità di risolvere problemi NP con una quantità di risorse, che possono essere energia o tempo, che non cresce esponenzialmente con la dimensione del problema. Questa assunzione è motivata dalle conseguenze che porterebbe una soluzione efficiente dei problemi NP: dimostrazione automatica in tempi ragionevoli, possibilità di distinguere sempre sequenze casuali da sequenze pseudocasuali, e così via. Intuitivamente può essere formulato in questo modo: la nostra capacità di estrarre informazione nell'universo è limitata dalla forma delle leggi fisiche.
Quello enunciato da Scott è quindi un principio fisico, e non un teorema matematico ;)

[CioKKoBaMBuZzo]

finalmente è arrivato banus :asd:

l'impossibilità di risolvere "efficientemente" (con risorse non esponenziali) i problemi NP è preso come principio fisico, dal quale si traggono varie conseguenze.
[...]
Molte teorie di gravità quantistica ipotizzano deviazioni non lineari della fisica quantistica in regimi non esplorati dagli esperimenti, e questa considerazione può essere rilevante per valutarne le conseguenze.
quindi o tutte queste teorie vanno scartate o i problemi np sono risolvibili con risorse polinomiali?
bhè a questo punto sarebbe meglio che i problemi np non fossero risolvibili con risorse polinomiali, così si farebbe un po' di pulizia e ci sarebbe una linea giuda in più per l'unificazione

non è che sai dirci pure quali teorie prevedono un comportamento non lineare della fisica quantistica e quali invece no?

[D.O.S.]

In realtà come ho detto sopra l'assunzione di Scott non è P<>NP, che dipende dal un particolare modello di computazione (macchina di Turing deterministica), ma in generale l'impossibilità di risolvere problemi NP con una quantità di risorse, che possono essere energia o tempo, che non cresce esponenzialmente con la dimensione del problema. Questa assunzione è motivata dalle conseguenze che porterebbe una soluzione efficiente dei problemi NP: dimostrazione automatica in tempi ragionevoli, possibilità di distinguere sempre sequenze casuali da sequenze pseudocasuali, e così via. Intuitivamente può essere formulato in questo modo: la nostra capacità di estrarre informazione nell'universo è limitata dalla forma delle leggi fisiche.
Quello enunciato da Scott è quindi un principio fisico, e non un teorema matematico ;)

detto così ha già più senso ma non mi sembra un principio fisico quanto piuttosto una visione filosofica dell'universo ... anche abbastanza pessimistica e viziata dal fatto che attualmente abbiamo una conoscenza parziale e non certo completa di questo.

una domanda : supponiamo che in futuro sarà dimostrata l'NP completezza del problema della fattorizzazione, quindi con un calcolatore quantistico sarà possibile risolvere in tempo polimoniale tutti i problemi NP .... ciò comporterebbe in ogni caso una quantità di risorse (energia ?) esponenziali ?

[Banus]

quindi o tutte queste teorie vanno scartate o i problemi np sono risolvibili con risorse polinomiali?
Esatto... dal momento che gli scienziati considerano la soluzione efficiente di problemi NP come un "regalo" troppo bello, queste considerazioni possono vincolare la scelta della teoria (non essendo disponibili dati sperimentali, solo i principi possono guidare l'intuizione).

non è che sai dirci pure quali teorie prevedono un comportamento non lineare della fisica quantistica e quali invece no?
Teoria delle stringhe e della gravità quantistica a loop, almeno nella loro formulazione standard, e in generale tutte le teorie che adottano la "somma sulle geometrie" assumono un comportamento lineare della meccanica quantistica. Un comportamento non lineare è presente in teorie più "esotiche" che sfruttano altri schemi di quantizzazione; non sono particolarmente popolari per quanto ne so :p

detto così ha già più senso ma non mi sembra un principio fisico quanto piuttosto una visione filosofica dell'universo ... anche abbastanza pessimistica e viziata dal fatto che attualmente abbiamo una conoscenza parziale e non certo completa di questo.
Ho scelto di definirlo principio fisico perché può essere verificato sperimentalmente: la dimostrazione di P=NP, unita alla capacità di costruire agevolmente computer (polinomialmente) equivalenti alla macchina di Turing deterministica, lo confuterebbe. Allo stesso modo lo confuterebbe un computer capace di sfruttare un'eventuale non-linearità della fisica quantistica.
Riguardo al pessimismo, le opinioni sono soggettive, ma personalmente considero di gran lunga più pessimistica la visione ispirata dal secondo principio della termodinamica, cioè il fatto di avere solo una riserva finita di energia utile. E' proprio l'entropia a rendere così pessimistico il quadro delineato da Aaronson: se energia o tempo non fossero limitati, non sarebbe un problema aspettare un tempo esponenzialmente lungo :D

una domanda : supponiamo che in futuro sarà dimostrata l'NP completezza del problema della fattorizzazione, quindi con un calcolatore quantistico sarà possibile risolvere in tempo polimoniale tutti i problemi NP .... ciò comporterebbe in ogni caso una quantità di risorse (energia ?) esponenziali ?
No, perché un computer quantistico li risolverebbe in tempo e spazio (qubit) polinomiale. Una simile dimostrazione equivale a dire che la classe dei problemi risolvibili in tempo polinomiale da un computer quantistico (BQP) contiene NP. Ma per motivi simili a P = NP, questo risultato è considerato improbabile.
Ho usato il termine più generico "risorse" perché alcuni modelli (come il "membrane computing") sono in grado di risolvere i problemi NP in tempo polinomiale, sfruttando però un numero esponenziale di elementi.