Class Description

EP: NP with 2^k Accepting Paths

The class of decision problems solvable by an NP machine such that

1. If the answer is 'no,' then all computation paths reject.
2. If the answer is 'yes,' then the number of accepting paths is a power of two.

Contained in C₌P, and in Mod_kP for any odd k. Contains UP.

Defined in [BHR00].

Linked From

HalfP: RP With Exactly Half Acceptance

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' exactly 1/2 of computation paths accept.
2. If the answer is 'no,' all computation paths reject.

Significantly, the number of candidate witnesses is restricted to be a power of 2. (This is implicit if they are binary strings.)

Contained in RP, EP, and Mod_kP for every odd k. Contained in EQP by the Deutsch-Jozsa algorithm.

Defined in [BB92], where it was called C₌₌P[half] (C₌₌P being an alternative name for WPP, that apparently didn't catch on or stick). The name used here is from [BS00]. There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.

More about...