What is Algorithmic Complexity?
Algorithmic complexity, (computational complexity, or Kolmogorov complexity), is a foundational idea in both computational complexity theory and algorithmic information theory, and plays an important role in formal induction. The algorithmic complexity of a binary string is defined as the shortest and most efficient program that can produce the string. Though there are an infinite number of programs that can produce any given string, one program or group of programs will always be the shortest. There is no algorithmic way of finding the shortest algorithm that outputs a given string; this is one of the first results of computational complexity theory. Even so, we can make an educated guess. This result, (the computational complexity of a string), turns out to be very important for proofs related to computability. Since any physical object or property can in principle be described to near-exhaustion by a string of bits, objects and properties can be said to have algorithmic complexity a
