Difference between revisions of "Complexity Zoo:H"

From Complexity Zoo
Jump to navigation Jump to search
m (1 revision: Complexity zoo import.)
 
m (Fixing broken links and minor grammar errors.)
 
(4 intermediate revisions by 3 users not shown)
Line 13: Line 13:
 
Contained in [[Complexity Zoo:R#rp|RP]], [[Complexity Zoo:E#ep|EP]], and [[Complexity Zoo:M#modkp|Mod<sub>k</sub>P]] for every odd k.  Contained in [[Complexity Zoo:E#eqp|EQP]] by the Deutsch-Jozsa algorithm.
 
Contained in [[Complexity Zoo:R#rp|RP]], [[Complexity Zoo:E#ep|EP]], and [[Complexity Zoo:M#modkp|Mod<sub>k</sub>P]] for every odd k.  Contained in [[Complexity Zoo:E#eqp|EQP]] by the Deutsch-Jozsa algorithm.
  
Defined in [[zooref#bb92|[BB92]]], where it was called C<sub>==</sub>P[half].  The name used here is from [[zooref#BS00|[BS00]]].  There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.
+
Defined in [[zooref#bb92|[BB92]]], where it was called C<sub>==</sub>P[half] (C<sub>==</sub>P being an alternative name for [[Complexity Zoo:W#wpp|WPP]], that apparently didn't catch on or stick).  The name used here is from [[zooref#bs00|[BS00]]].  There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.
  
 
----
 
----
Line 38: Line 38:
 
The class of distributional problems solvable by a [[Complexity Zoo:P#p|P]] machine. Defined in {{zcite|Imp95}}, though he calls the class HP.
 
The class of distributional problems solvable by a [[Complexity Zoo:P#p|P]] machine. Defined in {{zcite|Imp95}}, though he calls the class HP.
  
Alternately, {{zcite|BT06}} define HeurP as being the set of tuples <math>(L,D)</math>, where <math>L</math> is a language and <math>D</math> is a distribution of problem instances, such that there exists an algorithm <math>A</math> satisfying two properties:
+
Alternately, {{zcite|BT06}} define HeurP as being the set of tuples <math>(L,D)</math>, where <math>L</math> is a language and <math>D</math> is a distribution of problem instances, such that there exists an algorithm <math>A</math> satisfying two properties, for every <math>\delta>0</math>:
* For every <math>n\in\mathbb{N}</math>, for every <math>x</math> in the support of <math>D</math>, and for every <math>\delta>0</math>, <math>A(x;n,\delta)</math> runs in time bounded by <math>\mathrm{poly}(n/\delta)</math>.
+
* For every <math>n\in\mathbb{N}</math>, for every <math>x</math> in the support of <math>D</math>, <math>A(x;n,\delta)</math> runs in time bounded by <math>\mathrm{poly}(n/\delta)</math>.
* For every <math>\delta>0</math>, <math>A(\cdot;\cdot,\delta)</math> is a heuristic algorithm for <math>(L,D)</math> whose error probability is bounded by <math>\delta</math>.
+
* <math>A(x;n,\delta)</math> is a heuristic algorithm for <math>(L,D)</math> whose error probability is bounded by <math>\delta</math>.
  
 
----
 
----
Line 70: Line 70:
 
----
 
----
 
===== <span id="ho" style="color:red">HO</span>: High-Order logic =====
 
===== <span id="ho" style="color:red">HO</span>: High-Order logic =====
High order logic is an extension of [[#Complexity_Zoo:S#SO|Second order]], [[#Complexity_Zoo:F#FO|First order]] where we add quantification over higher order variables.
+
High order logic is an extension of [[Complexity_Zoo:S#so|Second order]], [[Complexity_Zoo:F#fo|First order]] where we add quantification over higher order variables.
  
We define a relation of order <math>o</math> and arity <math>k</math> to be a subset of <math>k</math>-tuple of relation of order <math>o-1</math> and arity <math>k</math>. When <math>o=1</math> 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 <math>o</math> and arity <math>k</math> to <math>k</math> relations of order <math>o-1</math> and arity <math>a</math> and test of equality between two relations of the same order and arity.
+
We define a relation of order <math>o</math> and arity <math>k</math> to be a subset of <math>k</math>-tuple of relation of order <math>o-1</math> and arity <math>k</math>. When <math>o=1</math> 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 constants (first-order variables) and relations (second-order variables)). The atomic predicates now can be general application of relations of order <math>o</math> and arity <math>k</math> to <math>k</math> relations of order <math>o-1</math> and arity <math>a</math> and test of equality between two relations of the same order and arity.
  
<math>HO^o</math> is the set of formulae with quantification up to order O. <math>\Sigma^i_j</math>(resp. <math>\Pi_j^i</math>) is defined as the set of formula in <math>HO^{i+1}</math> beginning by an existantial (resp universal) quantifier followed by at most <math>j-1</math> alternation of quantifiers.
+
<math>HO^o</math> is the set of formulae with quantification up to order O. <math>\Sigma^i_j</math>(resp. <math>\Pi_j^i</math>) is defined as the set of formula in <math>HO^{i+1}</math> beginning by an existential (resp universal) quantifier followed by at most <math>j-1</math> alternation of quantifiers.
  
This class was define in [[zooref#ht06|[HT06]]], and it was proved that <math>\Sigma^i_j=\exp_2^{i-1}(n^O(1))^{\Sigma^P_{j-1}}</math> where <math>\Sigma^P_{j-1}</math> is the <math>j</math>th level of the [[Complexity_Zoo:P#ph|polynomial hierarchy]].
+
This class was defined in [[zooref#ht06|[HT06]]], and it was proved that <math>\Sigma^i_j=\exp_2^{i-1}(n^O(1))^{\Sigma^P_{j-1}}</math> where <math>\Sigma^P_{j-1}</math> is the <math>j</math>th level of the [[Complexity_Zoo:P#ph|polynomial hierarchy]].
 +
----
 +
 
 +
===== <span id="hvpzk" style="color:red">HVPZK</span>: Honest-Verifier [[Complexity Zoo:P#pzk|PZK]] =====
 +
The class of decision problems that have [[Complexity Zoo:P#pzk|PZK]] protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).
 +
 
 +
Contained in [[Complexity Zoo:P#pp|PP]] [[zooref#bhctv17|[BHCTV17]]].
 +
There is an oracle where it is not closed under complement [[zooref#bhctv17|[BHCTV17]]].
 
----
 
----
  

Latest revision as of 01:12, 19 April 2023

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References


Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform


HalfP - HeurBPP - HeurBPTIME(f(n)) - HeurDTIME(f(n)) - HeurP - HeurPP - HeurNTIME(f(n)) - HkP - HVSZK


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 ModkP 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.


HeurBPP: Heuristic BPP

The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPP machine.

[FS04] showed a strict hierarchy theorem for HeurBPP; thus, HeurBPP does not equal HeurBPTIME(nc) for any fixed c.


HeurBPTIME(f(n)): Heuristic BPTIME(f(n))

The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a BPTIME(f(n)) machine. Thus, HeurBPTIME(f(n)) has the same relationship with BPTIME as HeurDTIME.

Thus HeurBPP is the union of HeurBPTIME(nc) over all c.


HeurDTIME(f(n)): Heuristic DTIME

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].


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 , where is a language and is a distribution of problem instances, such that there exists an algorithm satisfying two properties, for every :

  • For every , for every in the support of , runs in time bounded by .
  • is a heuristic algorithm for whose error probability is bounded by .

HeurPP: Heuristic PP

The class of distributional problems solvable by a PP machine. Defined in [Ill95], though he calls the class HPP.


HeurNTIME(f(n)): Heuristic NTIME

Defined as HeurDTIME, but for non-deterministic heuristic algorithms.

NP is not contained in HeurNTIME() for any constants [Per07].


HkP: High Hierarchy In NP

The class of problems A in NP such that ΣkPA = Σk+1P; that is, adding A as an oracle increases the power of the kth level of the polynomial hierarchy by a maximum amount.

For all k, Hk is contained in Hk+1.

H0 consists exactly of the problems complete for NP under Cook reductions.

H1 consists exactly of the problems complete for NP under strong non-deterministic Turing reductions [Sch83].

Defined in [Sch83].

See also LkP.


HO: High-Order logic

High order logic is an extension of Second order, First order where we add quantification over higher order variables.

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 constants (first-order variables) and relations (second-order variables)). The atomic predicates now can be general application of relations 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 existential (resp universal) quantifier followed by at most alternation of quantifiers.

This class was defined in [HT06], and it was proved that where is the th level of the polynomial hierarchy.


HVPZK: Honest-Verifier PZK

The class of decision problems that have PZK protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).

Contained in PP [BHCTV17]. There is an oracle where it is not closed under complement [BHCTV17].


HVSZK: Honest-Verifier SZK

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).

Equals SZK [Oka96].