Algorithms: Tiny Yet Powerful
Algorithms are like equations
Lenore Blum is a famous computer scientist who is now at Carnegie-Mellon University. She is famous for her work with Smale and Shub on the ”Real P=NP Question” that we discuss in another post. This important work shows that there is a version of P=NP for computations over the real numbers. Also she is one of national leaders helping to get more women involved in Computer Science. Finally, she is part of the most well known family in all of computer science: her husband, Manny Blum, is a Turing Award winner, and her son, Arvim Blum, is one of best researchers in the world in machine learning.
The work of hers that I will discuss here happens to be some join work of ours. We noticed that ”algorithms are tiny”. Let me explain. Recall that the Gettysburg address is only 269 words and was delivered in just over two minutes. Short things can be very powerful. Here is a note we put together to explain the consequences of the fact that algorithms are “tiny”.
Algorithms: Tiny yet powerful – and we can’t live without them
The promise of information technology is intimately intertwined with advances in algorithms (methods for solving problems). Algorithms are different from software systems in a fundamental way. They are tiny. An algorithm that solves an important problem can be small enough to fit on a single piece of paper using normal sized handwriting. Microsoft’s operating system, Vista, is a collection of many programs that in total has close to 100 million lines of code. That’s roughly the equivalent of 10,000 hardback books. Vista’s code is a trade secret, but even if it wasn’t, it’s not clear a single person could ever understand it all. Algorithms are at the opposite end of the spectrum. A postcard is often enough. As such, algorithms can be shared, understood, analyzed –even proved correct. Algorithms are based on ideas. New algorithms must be based on new ideas, new ways to approach the problem, new thoughts. They often express a clear single thought that changes the way we look at the world. Algorithms are like equations. Albert Einstein’s famous equation,
is a part of the popular culture. Few non-experts are able to explain the exact meaning of this equation. But, when placed on a T-shirt, most recognize it. The equation is one of the most profound and most important discoveries of all time. For better or worse, the equation created the Atomic Age. The plans and blueprints for building a modern atomic reactor would be closer in size to Vista. But the equation that gives us the power to build the atomic reactor has just five symbols. Likewise, it is an algorithm that makes possible the modern cryptographic systems that are critical for e-commerce. Prime numbers form the backbone of these systems. The famous Miller and Rabin algorithm to test whether or not a number is prime contains just 61 words and fits in a box:
Tiny, powerful algorithms have built the foundations for giant companies:
The airline industry, the shipping and logistics industries (e.g., ), and the financial sector all rely on fast optimization, scheduling and pricing algorithms. Medical imaging devices to detect heart valve damage would not be possible without the fast Fourier Transform (FFT). The list goes on and on. New algorithms will drive yet unknown industries. They will be essential for creating new kinds of computing: petascale, nanoscale, quantum, bio, neuro, distributed, multicore. They speed up today’s technology while ushering in tomorrow’s. They will be key to facing the challenges arising from the ubiquitous collections of mega sized data sets. In virtually any field where computation is done, the long-run impact of algorithmic advances will, eventually, outrun even the impact or demise of Moore’s law. Natural processes such as the regulation of proteins, the dynamics of social networks, and the strategic behavior of companies are all fundamentally algorithmic in nature. Algorithmic theory provides powerful tools, as well as appropriate language and mindset to help understand these new domains. The monumental first mapping of the human genome was accomplished by Myers’ whole genome shotgun sequencing algorithm. Exploring the potential of algorithms lies at the heart of the million dollar question: Does P = NP?
While research to answer this question may seem esoteric, it lies behind our current ability to have private and secure electronic communications. Our ability to maintain security in the future will hinge on research seeking answers to this question. Advances in our deep understanding of the nature of computation will underlie and propel further advances in virtually every area of information technology.
Prove there is no algorithm for SAT that runs in polynomial-time and can be written down on a single piece of paper. You can make the paper by , if you wish. The writing has to be normal size. No tricks.
I claim that this challenge is completely hopeless. There is no way that anyone will be able to prove that such an algorithm does not exists. Note, says much more–it says that there is no algorithm at all of any length. The algorithm could be a trillion pages in length, or it could be one page. What is so shocking is that the Conventional Wisdom is confident, yet the one page challenge is appears to be hopeless. Does that bother you? I find it shocking that we cannot today rule out that there is a one-page algorithm that solves SAT.
I have often wondered if there is some hope to prove that restricted algorithms cannot compute SAT. By restricted I mean algorithms that can only have very simple “loop” structure for example. There may be a way to make this precise enough so that we could make some progress. Yet, the full one page challenge is currently out of reach.