Class Description

HeurDTIME_{${\displaystyle \delta }$}(f(n)): Heuristic DTIME

For functions ${\displaystyle f(n)}$ and ${\displaystyle \delta (n)}$, we say that tuple ${\displaystyle (L,D)\in {\mathsf{H}\mathsf{e}\mathsf{u}\mathsf{r}\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}}_{\delta }(f(n))}$, where ${\displaystyle L}$ is a language and ${\displaystyle D}$ is a distribution of problem instances, if there exists a heuristic deterministic algorithm ${\displaystyle A}$ such that for all ${\displaystyle x}$ in the support of ${\displaystyle D}$, ${\displaystyle A}$ runs in time bounded by ${\displaystyle f(n)}$ and with failure probability bounded by ${\displaystyle \delta (n)}$ [BT06].

Linked From 2 Classes

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

HeurNTIME_{${\displaystyle \delta }$}(f(n)): Heuristic NTIME

Defined as Heur_{${\displaystyle \delta }$}DTIME, but for non-deterministic heuristic algorithms.

NP is not contained in HeurNTIME_{${\displaystyle 1/2+1/n^a}$}(${\displaystyle n^c}$) for any constants ${\displaystyle a,c}$ [Per07].

More about...