TY - GEN

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

AU - Allender, Eric

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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.

AB - 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.

KW - Complexity theory

KW - Kolmogorov complexity

KW - Minimum Circuit Size Problem

UR - http://www.scopus.com/inward/record.url?scp=85081130667&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85081130667&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-41672-0_2

DO - 10.1007/978-3-030-41672-0_2

M3 - Conference contribution

AN - SCOPUS:85081130667

SN - 9783030416713

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 8

EP - 18

BT - Complexity and Approximation - In Memory of Ker-I Ko

A2 - Du, Ding-Zhu

A2 - Wang, Jie

PB - Springer

T2 - International Workshop on Complexity and Approximation, 2019

Y2 - 27 April 2019 through 28 April 2019

ER -