Lower Bounds
There is a trivial lower bound of Ω(n) for multiplying two n-bit numbers on a single processor; no matching algorithm (on conventional Turing machines) nor any better lower bound is known. Multiplication lies outside of AC0 for any prime p, meaning there is no family of constant-depth, polynomial (or even subexponential) size circuits using AND, OR, NOT, and MODp gates that can compute a product. This follows from a constant-depth reduction of MODq to multiplication. Lower bounds for multiplication are also known for some classes of branching programs.
Read more about this topic: Multiplication Algorithm
Famous quotes containing the word bounds:
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)
“Firmness yclept in heroes, kings and seamen,
That is, when they succeed; but greatly blamed
As obstinacy, both in men and women,
Whene’er their triumph pales, or star is tamed —
And ‘twill perplex the casuist in morality
To fix the due bounds of this dangerous quality.”
—George Gordon Noel Byron (1788–1824)