Short lists with short programs in short time

Bauwens, B; Makhlin, A; Vereshchagin, N; Zimand, M

Bauwens, B (reprint author), Natl Res Univ Higher Sch Econ, Dept Comp Sci, Kochnovskiy Proezd 3, Moscow 125319, Russia.

COMPUTATIONAL COMPLEXITY, 2018; 27 (1): 31

Abstract

Given a machine U, a c-short program for x is a string p such that U(p) = x and the length of p is bounded by c + (the length of a shortest program fo......

Full Text Link