Class Description

HeurBPP: Heuristic BPP

The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPP machine.

[FS04] showed a strict hierarchy theorem for HeurBPP; thus, HeurBPP does not equal HeurBPTIME(n^c) for any fixed c.

Linked From

HeurBPTIME(f(n)): Heuristic BPTIME(f(n))

The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPTIME(f(n)) machine. Thus, HeurBPTIME(f(n)) has the same relationship with BPTIME as HeurDTIME.

Thus HeurBPP is the union of HeurBPTIME(n^c) over all c.

More about...