CiteULike Search Register Log in
CiteULike is a free online bibliography manager. Register and you can start organising your references online.

NP-complete Problems and Physical Reality

by: Scott Aaronson
(12 February 2005)

X Abstract

Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.

View the full article here:

arXiv (abstract), arXiv (PDF)

This article has been bookmarked 18 times, initially on 2005-02-15.

2006-10-06 User NeilInCanadia , 1 note

Fun paper.

2006-10-06 02:11:16
2006-08-21 User camu
Group Crypto
Group Randomness
2006-05-30 User proportional
2006-05-24 User jrw
2006-04-23 User gane5h
2006-04-02 User BrendaChng
2006-03-22 User BarrosH
2005-12-01 User rsaarelm
2005-03-29 User ansobol
2005-03-08 User dsquared
2005-03-03 User DineshGaitonde
2005-02-23 User geomblog
2005-02-15 User rdhyee , 1 note

I've been long interested in the physical basis of computability -- and also the fundamental limits of computation. Kinda vague statements, I know. Maybe this article will ground me in the latest thinking.

2005-02-15 23:17:27
User A_Olympia
Group Philosophy_of_Information
Group Blog_and_Wiki_Research
Privacy Statement | Terms & Conditions
CiteULike organises scholarly (or academic) papers or literature and provides bibliographic (which means it makes bibliographies) for universities and higher education establishments. It helps undergraduates and postgraduates. People studying for PhDs or in postdoctoral (postdoc) positions. The service is similar in scope to EndNote or RefWorks or any other reference manager like BibTeX, but it is a social bookmarking service for scientists and humanities researchers.