Class Description

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.

Linked From

No class.