Scott Aaronson is the Head Zookeeper of the Complexity Zoo! So he knows about complexity classes and calculating complexity of algorithms inside out. Perhaps this knowledge doesn’t help him naturally calculate the informational complexity of the parts of scientific theories that are phrased in natural languages like English?
Just to be clear: there are two unrelated notions of “complexity” blurred together in the above comment. The Complexity Zoo discusses computational complexity theory—it discusses how the run-time of an algorithm scales with algorithm’s inputs (and thereby classes algorithms into P, EXPTIME, etc.).
Kolmogorov Complexity is unrelated: it is the minimum number of bits (in some fixed universal programming language) required to represent a given algorithm. Eliezer’s argument for MWI rests on Komogorov complexity and has nothing to do with computational complexity theory.
I’m sure Scort Aarsonson is familiar with both, of course; I just want to make sure LWers aren’t confused about it.
Just to be clear: there are two unrelated notions of “complexity” blurred together in the above comment. The Complexity Zoo discusses computational complexity theory—it discusses how the run-time of an algorithm scales with algorithm’s inputs (and thereby classes algorithms into P, EXPTIME, etc.).
Kolmogorov Complexity is unrelated: it is the minimum number of bits (in some fixed universal programming language) required to represent a given algorithm. Eliezer’s argument for MWI rests on Komogorov complexity and has nothing to do with computational complexity theory.
I’m sure Scort Aarsonson is familiar with both, of course; I just want to make sure LWers aren’t confused about it.
Complexity is mentioned very often on LW but there is no post that works out the different notions?
http://lesswrong.com/lw/jp/occams_razor/ http://lesswrong.com/lw/q3/decoherence_is_simple/
http://en.wikipedia.org/wiki/Computational_complexity_theory
Ben G. had some interesting thoughts on the topic in 1993.