brute force physics Was: cleversafe...

[David Wagner]

Alexander Klimov  wrote:
> A problem with this reasoning is that the physical world and the usual
> digital computers have exponential simulation gap (it is known at
> least in one direction: to simulate N entangled particles on a digital
> computer one needs computations exponential in N). This can be
> considered as a reason to suspect that physical world is
> non-polynomially faster than the usual computers (probably even to an
                                                    ^^^^^^^^^^^^^^^^^^^
> extent that all NP computations can be simulated).
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

It is a commonly-held myth that quantum computers could solve
NP-complete problems, but most experts who have studied the issue
believe this is probably not the case.  There is no reason to think
that quantum computation could solve all NP problems in polynomial
time, and in fact, there are good reasons to believe this is
likely not the case.

(Do note that factoring is not NP-complete.)

See, e.g.

http://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_complexity_theory

or for a more nuanced and deep treatment of these issues,

http://www.scottaaronson.com/papers/npcomplete.pdf

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE