×

zbMATH — the first resource for mathematics

On the computational complexity of small descriptions. (English) Zbl 0799.68085

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI