How to solve the unsolvable using the power of approximation
In short: When exact answers are too complex to compute, brilliant minds turn to estimation. From calculating car fuel efficiency to navigating massive data structures, the art of approximation uses simple reasoning to decode the world's most intricate phenomena without needing a supercomputer.
In complex scientific and engineering challenges, finding a perfect solution is often computationally impossible. This is particularly true in the study of directed acyclic graphs (DAGs), where counting the exact number of topological sorts is an NP-hard problem. To navigate this, researchers use Monte Carlo methods—a technique that relies on random sampling to provide approximate solutions for problems that resist exact computation. This approach mirrors the legendary Fermi approximation techniques, which use clever estimation to tackle problems that otherwise defy exact calculation.
One such approach involves identifying 'gaps' in a sort. A gap occurs when two nodes, $v_i$ and $v_{j,1}$, exist in a sort without a directed edge between them. While a simple estimate might suggest that reversing these nodes provides a second valid sort, this is often a flawed assumption. A more refined method involves estimating the specific fraction of sorts where one node precedes another, then recording that fraction to build a more constrained, accurate DAG. A crude way to estimate the total number of sorts is to count the number of gaps, denoted as $m_{gaps}$, and use the value $2^{m_{gaps}}$ as a rough guide.
The strength of these methods lies in their scalability and simplicity. By averaging results over multiple samples, the accuracy of these random estimates can be significantly improved. This philosophy of 'cheap calculus' and 'low-cost experiments' is not just for computer science; it is applied to everything from the biophysics of neurons and animal locomotion to predicting weather patterns and understanding prime numbers. The goal is to foster curiosity and use simple reasoning—like dimensional analysis or symmetry—to grasp the underlying mechanics of the universe. Techniques like divide and conquer, scaling, and extreme cases are also essential tools in this toolkit. These methods are frequently applied to study diverse fields such as machine flight and the complexities of weather systems.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: The Art of Approximation
- Also: The Art of Approximation in Science and Engineering | Electrical Engineering and Computer Science | MIT OpenCourseWare
- Also: The Art of Approximation
To cite this card, link to https://intellectplus.co.uk/app/ideas-the-art-of-approximation.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
