P algorithms with lower bounds

vznuri_at_yahoo.com
Date: 12/26/04

  • Next message: Nameless: "Re: Version 2.5 of the GOLD Parser Builder was just released" 
    Date: 25 Dec 2004 16:11:00 -0800

    hi all, despite studying the field for years,
    I dont know of almost any published
    nontrivial lower bounds for any algorithms in P.
    afaik, they are very rare in the literature.

    the Q: what are the best (highest) known lower bounds
    for any P time algorithms?

    the best lower bound I have heard of is one
    in "models of computation" by john savage, where
    he quotes a proof that boolean convolution takes
    n^(3/2) monotone circuit gates.

  • Next message: Nameless: "Re: Version 2.5 of the GOLD Parser Builder was just released"

    Relevant Pages

    • Re: P algorithms with lower bounds
      ... > nontrivial lower bounds for any algorithms in P. ... st-connectivity and comparison trees for sorting) and others on general ... Branching programs in a paper published in 1982. ...
      (comp.theory)
    • Re: How do you do arrays
      ... > 1, as did their ancestor, Fortran, although other lower bounds can be ... and algorithms are as if only 10 elements exist starting at ...
      (comp.lang.python)