Turing's paper on computing is field finding. So too are Feynman and Deutsch's papers on quantum computing.
-
-
(Provided that there is indeed no P time algorithm for factorization, which we don't really know yet afaik.)
-
No, we don't. Peter Sarnak and Dick Lipton apparently both think there is a fast algorithm for factorization. And given the progress over time on two related problems - discrete log & primality testing - I don't think it'd be that surprising.
End of conversation
New conversation -
-
-
Quantum computers obey the Church-Turing thesis. I guess you're thinking of the possibility they violate the strong Church-Turing thesis. (Side note: we have no proof factoring is hard on conventional computers. I wouldn't be hugely surprised if it's not.)
-
Exactly. Now the interesting question is if there is a class of problems that our universe can solve efficiently but classical computers cannot.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.