We are independent & ad-supported. We may earn a commission for purchases made through our links.
Advertiser Disclosure
Our website is an independent, advertising-supported platform. We provide our content free of charge to our readers, and to keep it that way, we rely on revenue generated through advertisements and affiliate partnerships. This means that when you click on certain links on our site and make a purchase, we may earn a commission. Learn more.
How We Make Money
We sustain our operations through affiliate commissions and advertising. If you click on an affiliate link and make a purchase, we may receive a commission from the merchant at no additional cost to you. We also display advertisements on our website, which help generate revenue to support our work and keep our content free for readers. Our editorial team operates independently of our advertising and affiliate partnerships to ensure that our content remains unbiased and focused on providing you with the best information and recommendations based on thorough research and honest evaluations. To remain transparent, we’ve provided a list of our current affiliate partners here.
Engineering

Our Promise to you

Founded in 2002, our company has been a trusted resource for readers seeking informative and engaging content. Our dedication to quality remains unwavering—and will never change. We follow a strict editorial policy, ensuring that our content is authored by highly qualified professionals and edited by subject matter experts. This guarantees that everything we publish is objective, accurate, and trustworthy.

Over the years, we've refined our approach to cover a wide range of topics, providing readers with reliable and practical advice to enhance their knowledge and skills. That's why millions of readers turn to us each year. Join us in celebrating the joy of learning, guided by standards you can trust.

What is Algorithmic Complexity?

Michael Anissimov
By
Updated: May 21, 2024
Views: 13,893
Share

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 as well. In fact, reducing the complexity of real-world objects to programs that produce the objects as output, is one way of viewing the enterprise of science. The complex objects around us tend to come from three main generating processes; emergence, evolution, and intelligence, with the objects produced by each tending towards greater algorithmic complexity.

Computational complexity is a notion frequently used in theoretical computer science to determine the relative difficulty of computing the solutions to wide classes of mathematical and logical problems. More than 400 complexity classes exist, and additional classes are continuously being discovered. The famous P = NP question concerns the nature of two of these complexity classes. Complexity classes include problems far more difficult than anything one might confront in mathematics up to calculus. There are many imaginable problems in computational complexity theory that would require a near-infinite amount of time to solve.

Algorithmic complexity and related concepts were developed in the 1960s by dozens of researchers. Andrey Kolmogorov, Ray Solomonoff and Gregory Chaitin made important contributions in the late 60s with algorithmic information theory. The principle of minimum message length, closely related to algorithmic complexity, provides much of the foundation of statistical and inductive inference and machine learning.

Share
All The Science is dedicated to providing accurate and trustworthy information. We carefully select reputable sources and employ a rigorous fact-checking process to maintain the highest standards. To learn more about our commitment to accuracy, read our editorial process.
Michael Anissimov
By Michael Anissimov
Michael Anissimov is a dedicated All The Science contributor and brings his expertise in paleontology, physics, biology, astronomy, chemistry, and futurism to his articles. An avid blogger, Michael is deeply passionate about stem cell research, regenerative medicine, and life extension therapies. His professional experience includes work with the Methuselah Foundation, Singularity Institute for Artificial Intelligence, and Lifeboat Foundation, further showcasing his commitment to scientific advancement.
Discussion Comments
Michael Anissimov
Michael Anissimov
Michael Anissimov is a dedicated All The Science contributor and brings his expertise in paleontology, physics, biology...
Learn more
Share
https://www.allthescience.org/what-is-algorithmic-complexity.htm
Copy this link
All The Science, in your inbox

Our latest articles, guides, and more, delivered daily.

All The Science, in your inbox

Our latest articles, guides, and more, delivered daily.