Class Description

FERT: Fixed Error Randomized Time

FERT and FPERT are parameterized classes. FERT formally defined as the class of decision problems of the form (x, k), decidable in polynomial time by a probabilistic Turing Machine such that

  1. If the answer is yes, the probability of acceptance is at least 1/2 + min(f(k),1/|x|c)
  2. If the answer is no, the probability of acceptance is at most 1/2

Here, f is an arbitrary function (from the reals to <0,1/2]).

Defined in [KW15]. Contains BPP and is contained in para-PP and in FPERT.

Linked From

FPERT: Fixed Parameter and Error Randomized Time

FERT and FPERT are parameterized classes. FPERT is formally defined as the class of decision problems of the form (x, k1, k2), decidable in time f1(k1) * p(|x|) by a probabilistic Turing Machine such that

  1. If the answer is yes, the probability of acceptance is at least 1/2 + min(f2(k2),1/|x|c)
  2. If the answer is no, the probability of acceptance is at most 1/2

Here, f1 and f2 are arbitrary functions (f2 from the reals to <0,1/2]) and p is a polynomial.

Defined in [KW15]. Contains FERT and FPT and is contained in para-NPPP.

More about...