Complexity Zoo:H - Revision history

Diego: Fixed ref. The previous was a conditional result.

2025-09-02T05:05:29Z

Fixed ref. The previous was a conditional result.

Satoshi Hada: /* HeurNTIME\delta(f(n)): Heuristic {{zcls|n|ntime}} */ move the to the right place

2025-05-04T07:11:55Z

HeurNTIME\delta(f(n)): Heuristic {{zcls|n|ntime}}: move the to the right place

Brendan.zember: Fixing broken links and minor grammar errors.

2023-04-19T01:12:49Z

Fixing broken links and minor grammar errors.

Huntermonroe: /* HeurP: Heuristic P */

2022-05-11T01:33:51Z

HeurP: Heuristic P

Jgrochow: /* HalfP: RP With Exactly Half Acceptance */ Added reference to WPP

2021-04-27T16:39:30Z

HalfP: RP With Exactly Half Acceptance: Added reference to WPP

Jgrochow: /* HalfP: RP With Exactly Half Acceptance */ Fixed capitalization on link to BS00

2021-04-27T16:33:16Z

HalfP: RP With Exactly Half Acceptance: Fixed capitalization on link to BS00

Tooplark at 18:42, 14 November 2020

2020-11-14T18:42:50Z

Admin: 1 revision: Complexity zoo import.

2012-11-18T03:10:30Z

1 revision: Complexity zoo import.

New page

__NOTOC__
{{CZ-Letter-Menu|H}}

===== HalfP: RP With Exactly Half Acceptance =====
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that
<ol>
<li>If the answer is 'yes,' exactly 1/2 of computation paths accept.</li>
<li>If the answer is 'no,' all computation paths reject.</li>
</ol>
Significantly, the number of candidate witnesses is restricted to be a power of 2. (This is implicit if they are binary strings.)

Contained in [[Complexity Zoo:R#rp|RP]], [[Complexity Zoo:E#ep|EP]], and [[Complexity Zoo:M#modkp|ModkP]] 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==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.

----

===== HeurBPP: Heuristic [[Complexity Zoo:B#bpp|BPP]] =====
The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a [[Complexity Zoo:B#bpp|BPP]] machine.

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

----
===== HeurBPTIME(f(n)): Heuristic [[Complexity Zoo:B#bptime|BPTIME]](f(n)) =====
The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a [[Complexity Zoo:B#bptime|BPTIME]](f(n)) machine. Thus, HeurBPTIME(f(n)) has the same relationship with {{zcls|b|bptime}} as [[#heurdtime|HeurDTIME]].

Thus [[#heurbpp|HeurBPP]] is the union of HeurBPTIME(nc) over all c.

----

===== HeurDTIME<math>\delta</math>(f(n)): Heuristic {{zcls|d|dtime}} =====
For functions <math>f(n)</math> and <math>\delta(n)</math>, we say that tuple <math>(L,D)\in\mathsf{HeurDTIME}_{\delta}(f(n))</math>, where <math>L</math> is a language and <math>D</math> is a distribution of problem instances, if there exists a heuristic deterministic algorithm <math>A</math> such that for all <math>x</math> in the support of <math>D</math>, <math>A</math> runs in time bounded by <math>f(n)</math> and with failure probability bounded by <math>\delta(n)</math> {{zcite|BT06}}.

----

===== HeurP: Heuristic [[Complexity Zoo:P#p|P]] =====
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:
* 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>\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>.

----

===== HeurPP: Heuristic [[Complexity Zoo:P#p|PP]] =====
The class of distributional problems solvable by a [[Complexity Zoo:P#p|PP]] machine. Defined in [[zooref#ill95|[Ill95]]], though he calls the class HPP.

----

===== HeurNTIME<math>\delta</math>(f(n)): Heuristic {{zcls|n|ntime}} =====
Defined as [[#heurdtime|Heur<math>\delta</math>DTIME]], but for non-deterministic heuristic algorithms.

{{zcls|n|np}} is not contained in HeurNTIME<math>1/2+1/{n^a}</math>(<math>n^c</math>) for any constants <math>a,c</math> {{zcite|Per07}}.
----

===== HkP: High Hierarchy In [[Complexity Zoo:N#np|NP]] =====
The class of problems A in [[Complexity Zoo:N#np|NP]] such that [[Complexity Zoo:P#ph|ΣkP]]A = [[Complexity Zoo:P#ph|Σ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 [[Complexity Zoo:N#np|NP]] under Cook reductions.

H1 consists exactly of the problems complete for [[Complexity Zoo:N#np|NP]] under strong non-deterministic Turing reductions [[zooref#sch83|[Sch83]]].

Defined in [[zooref#sch83|[Sch83]]].

See also [[Complexity Zoo:L#lkp|LkP]].

----
===== HO: 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.

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.

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

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

===== HVSZK: Honest-Verifier [[Complexity Zoo:S#szk|SZK]] =====
The class of decision problems that have [[Complexity Zoo:S#szk|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 [[Complexity Zoo:S#szk|SZK]] [[zooref#oka96|[Oka96]]].

← Older revision		Revision as of 05:05, 2 September 2025
Line 89:		Line 89:
	The class of decision problems that have [[Complexity Zoo:S#szk\|SZK]] protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).		The class of decision problems that have [[Complexity Zoo:S#szk\|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 [[Complexity Zoo:S#szk\|SZK]] [[zooref#~~oka96~~\|[~~Oka96~~]]].	+	Equals [[Complexity Zoo:S#szk\|SZK]] [[zooref#gsv98\|[GSV98]]].

@@ Line 49: / Line 49: @@
 ----
-===== <span id="heurntime" style="color:red">HeurNTIME<sub><math>\delta</math></sub></span>(f(n)): Heuristic {{zcls|n|ntime}} =====
+===== <span id="heurntime" style="color:red">HeurNTIME<sub><math>\delta</math></sub>(f(n))</span>: Heuristic {{zcls|n|ntime}} =====
 Defined as [[#heurdtime|Heur<sub><math>\delta</math></sub>DTIME]], but for non-deterministic heuristic algorithms.

@@ Line 70: / Line 70: @@
 ----
 ===== <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]].
 ----

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

← Older revision		Revision as of 18:42, 14 November 2020
Line 77:		Line 77:

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