Scott Aaronson

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 ...
more >>>

Daniel Dewey

We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore ... more >>>