[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...