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:

    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)

    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)