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

[My Computational Complexity Web Log] More on Kolmogorov Complexity

Expand Messages
  • Lance Fortnow
    There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won t put it here (but you might find it at the
    Message 1 of 1 , Apr 29, 2003
    • 0 Attachment
      There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won't put it here (but you might find it at the bottom of Sophie Laplante's web page). Reading the cartoon you might find it funny because not all strings seem equally random even if they are equally likely. Kolmogorov formalized this idea by measuring the randomness of a string x, denoted C(x), by the smallest program that generates x.

      At this Dagstuhl workshop there are many talk on a number of variations of Kolmogorov complexity. John Tromp had a nice presentation on the basic notion. He showed, among other things, that for any x you can find a constant length y such that C(xy)>C(x). This seems obvious but it is pretty tricky tor prove. Tromp's proof works by defining a new C-based measure on strings and using that to show that any string x has a small number of programs generating x that have length close to C(x) and using that fact to get his result. He doesn't have a write-up yet, but I'll keep a lookout for it.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 4/29/2003 4:13:17 AM

      Powered by Blogger Pro

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