Class Description

HeurDTIME(f(n)): Heuristic DTIME

For functions and , we say that tuple , where is a language and is a distribution of problem instances, if there exists a heuristic deterministic algorithm such that for all in the support of , runs in time bounded by and with failure probability bounded by [BT06].

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(nc) over all c.

More about...


HeurNTIME(f(n)): Heuristic NTIME

Defined as HeurDTIME, but for non-deterministic heuristic algorithms.

NP is not contained in HeurNTIME() for any constants [Per07].

More about...