Class Description

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

See also: BPPKT.

Linked From

BPPKT: 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 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.

More about...