×

zbMATH — the first resource for mathematics

Kolmogorov complexity and instance complexity of recursively enumerable sets. (English) Zbl 0859.03015

MSC:
03D15 Complexity of computation (including implicit computational complexity)
03D25 Recursively (computably) enumerable sets and degrees
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv