On Sat, May 28, 2011 at 7:05 PM, James A. Donald <jam...@echeque.com> wrote:
> On 28/05/11 03:37, James A. Donald wrote: > >> What can be said is that the class of problems soluble by a quantum >>> computer >>> is larger than the class of problems soluble by a classical computer. >>> >> > On 2011-05-29 9:01 AM, David-Sarah Hopwood wrote: > >> No, it can't: >> >> - for idealized quantum and classical computers (with unbounded memory >> running for unbounded time), those classes are identical. >> >> - for quantum and classical computers that can be practically built at >> any >> point in time, and with a limit on the time to find a solution, it >> certainly isn't clear that the class of problems soluble by quantum >> computers will be larger (ever). That depends on how big and fast you >> can make quantum computers and classical computers. >> > > What can be said is that the class of problems soluble by a quantum > computer with a polynomially large number of components in polynomial time > is larger than the class of problems soluble by a classical computer with a > polynomially large number of components in polynomial time. Wait, was P!=NP proven and I missed it? I thought it was merely an assertion with overwhelming evidence, but no formal proof. n
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
