Johnn ha scritto:
TigerShark ha scritto:
No, per niente.
Riferito a cosa?
TigerShark ha scritto:
Con l'algoritmo di Shor è possibile fattorizzare i numeri primi in O(log(n^3)) con un computer quantistico.
Quindi la soluzione con un computer quantistico è assolutamente fattibile.
Imho non importa la complessità, in questo discorso, purchè sia polinomiale. Basta avere una macchina di Touring non deterministia ed automaticamente si risolve qualsiasi problema NP in O(n) grazie all'enumerazione totale, no? Il problema è passare da 2^n a n^x non arrivare al lower bound teorico del problema, sempre in questo contesto.
La macchina di turing non deterministica non esiste.
Il computer quantistico, con un numero limitato di qubit, si.
Cita:
TigerShark ha scritto:
L'importanza maggiore di questa differenza tra P e NP era prima dei computer quantistici e degli algoritmi adattati ad essi.
Ora in un futuro non molto distante sarà praticamente inutile imho.
E ricordo che ad oggi computer quantistici con un pò di qubit sono stati costruiti e quindi sono esistenti. L'unica limitazione è che per utilizzare l'algoritmo di Shor servirebbe un computer quantistico con più qubit.
E comunque un computer quantistico non è proprio esattamente equivalente ad una macchina di touring non deterministica.
In cosa differisce un computer quantistico, che nonostante qualche esperimento, imho non c'è ancora, da una macchina di Touring non deterministica? Cioè quali sono i limiti del computer quantistico? Sono sostanziali o no? Perché gli NP sono cattivi: non basterebbe un grosso step computazionale per "sconfiggerli". Se il computer quantistico è solo un calcolatore fortemente parallelizzato, ammettiamo che in un attimo passiamo da 4-6 core di oggi a 100000 core tra 5 anni e 200000 core tra 6 anni e così via, non abbiamo risolto niente, se non trovare una soluzione di istanza leggermente superiore a quelle attuali dei problemi NP.
no, un computer quantistico è equivalente ad una macchina di turing quantistica e quindi è in grado di risolvere i problemi di classe PP.
Essi sono equivalenti ai problemi di tipo NP, però la soluzione non è esatta ma è probabilistica.
Ad esempio l'algoritmo di Shore garantisce un errore inferiore al 33%.
In un computer classico puoi aumentare il numero di core, la frequenza, la potenza delle unità logiche, ma sarà sempre equivalente ad una macchina di turing deterministica, e quindi, per definizione, potrà risolvere in tempo polimoniale solo i problemi di classe P.
Una macchina di turing quantistica invece potrà risolvere con una buona percentuale di confidenza dei problemi di classe NP in tempo polinomiale, mentre la macchina di turing non deterministica li potrà risolvere in maniera esatta.
Questa è essenzialmente la differenza tra un computer quantistico ed una macchina di turing non deterministica, ma dal punto di vista dell'espressività, se non consideriamo la probabilità della soluzione che non è mai uguale ad 1, sono praticamente equivalenti.
Ad oggi questa dimostrazione dell'equivalenza tra le classi P ed NP è molto importante, ma in un futuro prossimo imho non lo sarà più proprio per questo motivo.
spero che ora sia un pò più chiaro quello che intendevo.
Login
Chat [0]
FAQ
Cerca
, qualcosa è già uscito fuori, è da vedere se è sostanziale o correggibile.
