Multiplication Algorithm - Lower Bounds

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:

    What comes over a man, is it soul or mind
    That to no limits and bounds he can stay confined?
    You would say his ambition was to extend the reach
    Clear to the Arctic of every living kind.
    Why is his nature forever so hard to teach
    That though there is no fixed line between wrong and right,
    There are roughly zones whose laws must be obeyed?
    Robert Frost (1874–1963)

    How far men go for the material of their houses! The inhabitants of the most civilized cities, in all ages, send into far, primitive forests, beyond the bounds of their civilization, where the moose and bear and savage dwell, for their pine boards for ordinary use. And, on the other hand, the savage soon receives from cities iron arrow-points, hatchets, and guns, to point his savageness with.
    Henry David Thoreau (1817–1862)