BPP with an oracle that, given a string x, returns the minimum over all programs P that output xi on input i, of the length of P plus the maximum time taken by P on any input.
A similar class was defined in [ABK+02], where it was also shown that in BPPKT one can factor, compute discrete logarithms, and more generally invert any one-way function on a non-negligible fraction of inputs.
See also: PK.
P equipped with an oracle that, given a string x, returns the length of the shortest program that outputs x.
A similar class was defined in [ABK+02], where it was also shown that PK contains PSPACE. It is not known whether PK contains all of R, or even any recursive problem not in PSPACE.
See also: BPPKT.