Class Description

HeurP: Heuristic P

The class of distributional problems solvable by a P machine. Defined in [Imp95], though he calls the class HP.

Alternately, [BT06] define HeurP as being the set of tuples ${\displaystyle (L,D)}$, where ${\displaystyle L}$ is a language and ${\displaystyle D}$ is a distribution of problem instances, such that there exists an algorithm ${\displaystyle A}$ satisfying two properties, for every ${\displaystyle \delta >0}$:

• For every ${\displaystyle n\in \mathbb {N} }$, for every ${\displaystyle x}$ in the support of ${\displaystyle D}$, ${\displaystyle A(x;n,\delta )}$ runs in time bounded by ${\displaystyle \mathrm {poly} (n/\delta )}$.
• ${\displaystyle A(x;n,\delta )}$ is a heuristic algorithm for ${\displaystyle (L,D)}$ whose error probability is bounded by ${\displaystyle \delta }$.

Linked From

AvgP: Average Polynomial-Time

A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.

A function f, from strings to integers, is polynomial on μ-average if there exists a constant ε>0 such that the expectation of f^ε(x) is finite, when x is drawn from μ.

Then (A,μ) is in AvgP if there is an algorithm for A whose running time is polynomial on μ-average.

This convoluted definition is due to Levin [Lev86], who realized that simpler definitions lead to classes that fail to satisfy basic closure properties. Also see [Gol97] for more information.

If AvgP = DistNP then EXP = NEXP [BCG+92].

Strictly contained in HeurP [NS05].

See also: (NP,P-samplable).

More about...