View source

From Qwiki

You do not have permission to do that, for the following reason:
The action you have requested is limited to users in one of the groups user, zoo.
You can view and copy the source of this page:
__NOTOC__
{{CZ-Letter-Menu|H}}


===== <span id="halfp" style="color:red">HalfP</span>: 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|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.

----

===== <span id="heurbpp" style="color:red">HeurBPP</span>: 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]](n<sup>c</sup>) for any fixed c.

----
===== <span id="heurbptime" style="color:red">HeurBPTIME(f(n))</span>: 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(n<sup>c</sup>) over all c.

----

===== <span id="heurdtime" style="color:red">HeurDTIME<sub><math>\delta</math></sub>(f(n))</span>: 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}}. 

----

===== <span id="heurp" style="color:red">HeurP</span>: 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>.

----

===== <span id="heurpp" style="color:red">HeurPP</span>: 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.

----

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

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

===== <span id="hkp" style="color:red">H<sub>k</sub>P</span>: 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|&#931;<sub>k</sub>P]]<sup>A</sup> = [[Complexity Zoo:P#ph|&#931;<sub>k+1</sub>P]]; that is, adding A as an oracle increases the power of the k<sup>th</sup> level of the polynomial hierarchy by a maximum amount.

For all k, H<sub>k</sub> is contained in H<sub>k+1</sub>.

H<sub>0</sub> consists exactly of the problems complete for [[Complexity Zoo:N#np|NP]] under Cook reductions.

H<sub>1</sub> 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|L<sub>k</sub>P]].

----

===== <span id="hvszk" style="color:red">HVSZK</span>: 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]]].
Templates used on this page:
Return to Complexity Zoo:H.
Retrieved from "http://qwiki.stanford.edu/wiki/Complexity_Zoo:H"
View source

From Qwiki

Views

Personal tools

Navigation

Search

Toolbox
