Class Description

P^K: P With Kolmogorov-Complexity Oracle

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 P^K contains PSPACE. It is not known whether P^K contains all of R, or even any recursive problem not in PSPACE.

See also: BPP^KT.

Linked From

BPP^KT: BPP With Time-Bounded Kolmogorov Complexity Oracle

BPP with an oracle that, given a string x, returns the minimum over all programs P that output x_i 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 BPP^KT one can factor, compute discrete logarithms, and more generally invert any one-way function on a non-negligible fraction of inputs.

See also: P^K.

More about...