cooper@pbsvax.DEC (Topher Cooper HLO2-3/M08 DTN225-5819) (03/06/85)
In the 25 February, 1985 (Volume 54, Number 8) issue of Physical Review
Letters, there is an article by Stephen Wolfram entitled "Undecidability
and Intractability in Theoretical Physics" (pages 735-738). It is
generally a good article but one footnote particularly caught my eye:
"5. It is just possible, however, that the parallelism of the
path integral may allow quantum mechanical systems to solve
any NP problem in polynomial time."*
This is an interesting idea. Does anyone want to propose an idealized
computer for solving NP (complete/hard) problems in polynomial time
using quantum effects? These should be similar in form and level of
detail to the "reversible" computers being proposed in discussions of
the theoretical minimum energy needed for computation.
Topher Cooper
USENET: ...{allegra,decvax,ihnp4,ucbvax}!decwrl!dec-rhea!dec-pbsvax!cooper
ARPA/CSNET: cooper%pbsvax.DEC@decwrl
--------------------------------------
* Ibid p.738. Copyright 1985 The American Physical Society. This is
quoted under the clause of the copyright statement in Physical Review
Letters which states: "Permission is granted to quote from this journal
with the customary acknowledgment of the source."