This paper proposes to eliminate model-dependence from complexity theory by studying a "best possible" model of computation that takes advantages of all the affordances and obeys all the restrictions of known physics. The computational complexity that we derive for problems in our model can be considered to represent the true difficulty, within a constant factor, of solving those problems with the best possible computing technology that is consistent with the known physics of our universe.
Working draft:
This paper is part of the M series of working memos produced by the MIT Reversible Computing Project.