No label defined (Q5465360)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2196513
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2196513 |
Statements
22 August 2005
0 references
complexity classes
0 references
P-printable sets
0 references
P/poly
0 references
0.7890610098838806
0 references
0.7853983044624329
0 references
0.7744947671890259
0 references
0.7718155980110168
0 references
The paper gives a survey about a number of interesting connections between Kolmogorov Complexity (KC) and computational complexity apart from the incompressibility method. It presents a catalogue of many time-bounded variants of KC. It shows how instance complexity compares to time-bounded KC, and how time-bounded KC can be used to characterize the sizes of efficiently computable sets. Moreover, Levin's universal search is looked at from the Kolmogorov perspective, and KC is used to characterize some complexity classes, in particular the P-printable sets and P/poly. For the entire collection see [Zbl 1062.68004].
0 references
