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 Heur
DTIME, but for non-deterministic heuristic algorithms.
NP is not contained in HeurNTIME
(
) for any constants
[Per07].
More about...