Difference between revisions of "Complexity Zoo:H"
m (1 revision: Complexity zoo import.)
Latest revision as of 22:10, 17 November 2012
 HalfP: RP With Exactly Half Acceptance
The class of decision problems solvable by an NP machine such that
- If the answer is 'yes,' exactly 1/2 of computation paths accept.
- 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.)
Defined in [BB92], where it was called C==P[half]. 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.
The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPP machine.
Thus HeurBPP is the union of HeurBPTIME(nc) over all c.
For functions and , we say that tuple , where is a language and is a distribution of problem instances, if there exists a heuristic deterministic algorithm such that for all in the support of , runs in time bounded by and with failure probability bounded by [BT06].
Alternately, [BT06] define HeurP as being the set of tuples , where is a language and is a distribution of problem instances, such that there exists an algorithm satisfying two properties:
- For every , for every in the support of , and for every , runs in time bounded by .
- For every , is a heuristic algorithm for whose error probability is bounded by .
Defined as HeurDTIME, but for non-deterministic heuristic algorithms.
For all k, Hk is contained in Hk+1.
H0 consists exactly of the problems complete for NP under Cook reductions.
Defined in [Sch83].
See also LkP.
 HO: High-Order logic
We define a relation of order and arity to be a subset of -tuple of relation of order and arity . When it is by extension a first order variable. The quantification of formula in HO is over a given order (which is a straightforward extension of SO where we add quantification over constant (first-order variable) and relation (second-order variables). The atomic predicates now can be general application of relation of order and arity to relations of order and arity and test of equality between two relations of the same order and arity.
is the set of formulae with quantification up to order O. (resp. ) is defined as the set of formula in beginning by an existantial (resp universal) quantifier followed by at most alternation of quantifiers.
The class of decision problems that have SZK protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).