• DocumentCode
    2517639
  • Title

    The generalized Kolmogorov complexity of sets

  • Author

    Allender, Eric

  • Author_Institution
    Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA
  • fYear
    1989
  • fDate
    19-22 Jun 1989
  • Firstpage
    186
  • Lastpage
    194
  • Abstract
    Recent work has shown that it is useful to consider new variants of time-bounded Kolmogorov complexity. The author reviews that work, presents the new definitions, and studies the basic properties of these measures. He deals with the function KL, which measures the complexity of the simplest strings in the language L and with sets of the form KUv[s(n ),t(n)], which consists of strings with unique short descriptions
  • Keywords
    computational complexity; generalized Kolmogorov complexity of sets; language L; simplest strings; strings; unique short descriptions; Computer science; Length measurement; Machinery; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
  • Conference_Location
    Eugene, OR
  • Print_ISBN
    0-8186-1958-9
  • Type

    conf

  • DOI
    10.1109/SCT.1989.41824
  • Filename
    41824
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2517639