#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

9 March, 18:30 MSK

We will continue the talk of Alexey Milovanov

Limit on the computational power of C-random strings.

Informally, the Kolmogorov complexity of a string x is defined as the minimal length of a program that outputs x on the empty input. This concept allows us to define the notion of an individual random string. Specifically, a string x is called random if its Kolmogorov complexity is at least the length of x. Let R denote the set of all random strings. A natural question is: how powerful is the oracle R? For example, what languages belong to P^R?

These and similar questions have been investigated in the works of Allender, Hirahara, and others. For example, it was shown that for every universal decompressor of plain complexity U, the class P^{R_U} contains NEXP.

However, no non-trivial upper bounds for P^{R_U} were previously known: it was not even known whether there is any universal U such that the halting problem does not belong to P^{R_U}. In this talk, it will be shown that such a U exists, which solves one of the open questions posed here: https://people.cs.rutgers.edu/~allender/papers/sigact.news.draft.pdf

➰ ВК