Scott Aaronson [sier](https://scottaaronson.com/writings/randi.html): > The Kolmogorov complexity of a piece of information is defined to be the length of the shortest computer program that outputs that information. Fra [denne Quanta-artikkelen](https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/): > “We think that we know what we mean when we say, ‘That thing is random,’” Allender said. “But it wasn’t really until the notion of Kolmogorov complexity was defined that that was shown to have a mathematically meaningful definition.” > > To get at the notion of a random string of numbers, Andrey Kolmogorov decided in the 1960s to focus not on the process by which the string was generated, but on the ease with which it can be described. The string 99999999999999999999 can be concisely described as “20 9s,” but the string 03729563829603547134 might not have any description shorter than the string itself. > > Kolmogorov defined the complexity of a string as the length of the shortest possible program that produces the string as an output. If we’re dealing with, say, thousand-digit strings, some have very short programs, such as “print a thousand 9s” or “print the number 23319” or “print the first thousand digits of π using the following formula….” Other strings are impossible to describe succinctly and have no program shorter than one that writes out the entire string and just tells the computer to print it. And some strings have programs whose length falls somewhere in the middle. Tett knyttet til eksistensen av [[Énveisfunksjoner]]. > There’s just one drawback to Kolmogorov complexity: It’s incomputable, meaning that there is no program that can calculate the complexity of every possible string. We know this because if there were such a program, we’d end up with a contradiction. Makes sense. > To see this, imagine we have a program that can compute Kolmogorov complexity for any string. Let’s call the program K. Now, let’s search for the smallest string of numbers — call it S — whose Kolmogorov complexity is double the length of K. To be concrete, we could imagine that K has 1 million characters, so we’re looking for a string S whose Kolmogorov complexity is 2 million (meaning that the shortest program that outputs S has 2 million characters). > > With program K in our toolbox, calculating S is easy (though not necessarily quick): We can write a new program that we’ll call P. The program P essentially says, “Go through all strings in order, using program K to compute their Kolmogorov complexity, until you find the first one whose Kolmogorov complexity is 2 million.” We’ll need to use program K when building P, so altogether P will have slightly more than 1 million characters. But this program outputs S, and we defined S as a string whose shortest program has 2 million characters. There’s the contradiction. Huh (emphasis added): > But (...) the program P takes an enormous amount of time to run, since it has to check so many strings. If we forbid such slow programs, we end up with a notion called “time-bounded” Kolmogorov complexity. **This version of Kolmogorov complexity is computable** — we can calculate the time-bounded Kolmogorov complexity for every possible string, at least in principle. And in some ways, it is as natural a concept as the original Kolmogorov complexity. > > Since time-bounded Kolmogorov complexity is computable, a natural next question is how hard it is to compute. [[Énveisfunksjoner|And this is the question that Liu and Pass proved holds the key to whether one-way functions exist.]] “It’s a lovely insight,” Allender said.