Ker-I ko and the study of resource-bounded kolmogorov complexity

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Ker-I Ko was among the first people to recognize the importance of resource-bounded Kolmogorov complexity as a tool for better understanding the structure of complexity classes. In this brief informal reminiscence, I review the milieu of the early 1980’s that caused an up-welling of interest in resource-bounded Kolmogorov complexity, and then I discuss some more recent work that sheds additional light on the questions related to Kolmogorov complexity that Ko grappled with in the 1980’s and 1990’s. In particular, I include a detailed discussion of Ko’s work on the question of whether it is NP-hard to determine the time-bounded Kolmogorov complexity of a given string. This problem is closely connected with the Minimum Circuit Size Problem (MCSP), which is central to several contemporary investigations in computational complexity theory.

Original languageEnglish (US)
Title of host publicationComplexity and Approximation - In Memory of Ker-I Ko
EditorsDing-Zhu Du, Jie Wang
PublisherSpringer
Pages8-18
Number of pages11
ISBN (Print)9783030416713
DOIs
StatePublished - Jan 1 2020
EventInternational Workshop on Complexity and Approximation, 2019 - Qingdao, China
Duration: Apr 27 2019Apr 28 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12000 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Workshop on Complexity and Approximation, 2019
CountryChina
CityQingdao
Period4/27/194/28/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Complexity theory
  • Kolmogorov complexity
  • Minimum Circuit Size Problem

Fingerprint Dive into the research topics of 'Ker-I ko and the study of resource-bounded kolmogorov complexity'. Together they form a unique fingerprint.

Cite this