NancyLebovitz comments on What I've learned from Less Wrong - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (232)
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.