The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
Kolmogorov Complesity and Instance Complexity of Recursively Enumerable Sets
Mrtin Kummer,
Pages. 1123-1143
Abstract
Contents 1. Introduction
2. Notation and definitions
3. A version of Barzdin's lemma
4. The ICC fails
5. R.e. sets with hard instances
6. Open questions
Key words Kolmogorov complexity, instance complexity, recursively enumerable sets, complete sets.
Mathmatical Subject Classification 03D15, 03D32, 68Q15