Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Blum Complexity Measures

Expand Messages
  • Lance Fortnow
    The Blum speed-up theorem states that there exists a computable language L such that if L is in time t(n) then L is in time log(t(n)). The log function can be
    Message 1 of 1 , Apr 5 6:10 AM
    • 0 Attachment
      The Blum speed-up theorem states that there exists a computable language L such that if L is in time t(n) then L is in time log(t(n)). The log function can be replaced by any arbitrarily slowly growing computable function. Instead of time one can use space or any other measure Φ that fulfills these properties:
      1. Φ(M,x) is finite if and only if M(x) halts, and
      2. There is a computable procedure that given (M,x,r) can decide if Φ(M,x)=r.
      These are known as Blum axioms and measures that fulfill them are known as Blum complexity measures. They were developed by Manuel Blum in the late 1960's.

      The Borodin-Trakhtenbrot Gap Theorem states that given any computable function g(n) (e.g. g(n)=2^n), there exists a function t(n) such that every language computable in time g(t(n)) is also computable in time t(n), i.e., there exists a gap between these time classes. Once again the theorem holds for any Blum complexity measure.

      We don't see much of the Blum complexity measures these days for a few reasons.

      1. The only truly interesting Blum measures are time and space.
      2. The functions and languages that one gets out of the speed-up, gap and related theorems are usually quite large and artificial.
      3. Many measures that we are interested in today, like the number of random coins used by a probabilistic Turing machine, do not fulfill the Blum axioms.
      In 1991 I saw Manuel Blum give a talk discussing a new complexity measure, something about mind changes, that did not fulfill his axioms. So we had a Blum complexity measure that was not a Blum complexity measure and as Douglas Adams would say Manuel Blum "promptly vanishes in a puff of logic." [Just kidding-we like Manuel]

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 4/5/2004 08:06:26 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.