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:
“Great Wits are sure to Madness near alli’d
And thin Partitions do their Bounds divide;
Else, why should he, with Wealth and Honour blest,
Refuse his Age the needful hours of Rest?”
—John Dryden (1631–1700)
“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)