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”.
The Note
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:
, an odd integer greater than 
. Write 
as 
by factoring out powers of 
. Pick 
randomly in the range 
. If 
or 
for some 
in the range 
, then return probably prime. Else return composite.
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.
A Challenge
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 
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, 
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.
Is this answer on the chalenge: arXiv:cs/0703146v3 [cs.CC] )
I believe that this paper shows that a particular algorithm does not work for SAT. I do not see how this solves the challenge.
Well, dear rjlipton,
“Believe”, “see” … – and what about just reading?
My apologies to Mr. Gubin for being so harsh in what follows below, but it needs to be said. Mr. Gubin, I suggest that if you decide to write more on the subject of solving NP-hard problems that you at least test your algorithms before you claim that they’re correct and exact. There’s a lot of work to be done on solving NP-hard problems, and negligently wasting people’s time with completely invalid conjecture is abhorrent. My guess is that you could actually make a positive contribution if you put your mind to it, but you’ve now given yourself an uphill battle to regain trust.
Mr. Lipton, having read and laughed at a few papers by Mr. Gubin for how trivially incorrect they were, I suggest that it is not even worth your time to read his papers. One algorithm that he claimed was an algorithm to solve 3-SAT exactly in O(n^3) gives the wrong answer for an instance of only 3 clauses. After numerous people pointed this out, he then produced another algorithm that was less obviously wrong, but I spent the hour or two to implement it, and it produced the wrong answer for the first random instance of 10 clauses I gave it. It produced incorrect answers for some of the other few instances I input, so I simply stopped reading his papers.
I suppose that I should have expected as much from papers without rigorous proofs of correctness, but I wanted to be absolutely sure. Others have written extensively on the incorrectness of his algorithms (e.g. http://arxiv.org/PS_cache/arxiv/pdf/0804/0804.2699v1.pdf), so I’m absolutely shocked that he’s still peddling them.
Dear Mr. Dickson,
Would you like to replay on this message with your counter example? I would like to check your claim by myself.
Thank you
One counterexample is presented in the paper to which I linked above. Alternatively, just generate a few dozen random instances of size 100 that are satisfiable and a few dozen random instances of size 100 that are not satisfiable, and odds are high that several from one of the two groups will be counterexamples to your algorithm’s exactness. Just solve it with any real 3-SAT solver and with your algorithm, and you’ll see that they produce different results.
For your original 3-SAT algorithm, the instance a/\b/\(-a\/-b), or the expansion of it to have all clauses with 3 literals, is a counterexample (i.e. the algorithm says that it is satisfiable, but it is clearly not). For your TSP algorithm, a lengthy paper on the incorrectness of it is at http://arxiv.org/ftp/cs/papers/0610/0610125.pdf
Well, Mr. Dickson,
There is a 3SAT solver utilizing my algorithm. It is at www_dot_timescube_dot_com.
So, if you don’t want post your examples, you may check them by yourself using the demo.
I don’t know about 100 clauses, but it will do 40 clauses on Chrome, Safari, or other fast browser (you even may use IE for 20 clauses or so). It is a client-side java script, so all depends on your computer. You may “View Source” before using it (sorry, it little hasty – it was done in couple hours or so).
Dear Mr. Dickson, it (really) will be OK if the algorithm will resolve all your examples correctly. Anybody is entitled on mistakes, and… misunderstanding of readers especially when they do not read up to end :).
Anyway, post or send me any real counter example. I would really appreciate it.
Thank you for your attention to my work.
Wow, I don’t know why I’m wasting my time on you, because you’re evidently a con man. I just gave you links to two papers giving thoroughly-explained counterexamples to your work, and you pretend that they don’t exist. Do you never stop to consider that you might be wrong? From now on I’m taking Oded Goldreich’s advice and not reading any papers claiming to solve P vs. NP (http://www.wisdom.weizmann.ac.il/~oded/p-vs-np.html) I’ll keep using your papers as an example of how the reliability of papers on arxiv is generally low.
My apologies to Mr. Lipton for this ridiculousness.
Unfortunately I cannot weigh in on the heated debate between Mr. Gubin and Mr. Dickson, but I must dispute a claim made by Dr. Lipton in the text of this post. The claim is: “The famous Miller and Rabin algorithm to test whether or not a number is prime contains just 61 words and fits in a box:”
I have viewed this page now in four modern browsers (Firefox, IE8, Opera,Chrome) and in none of them does the algorithm fit in the given box!