https://complexityzoo.net/index.php?title=Complexity_Zoo:H&feed=atom&action=historyComplexity Zoo:H - Revision history2024-03-29T12:52:07ZRevision history for this page on the wikiMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Zoo:H&diff=6855&oldid=prevBrendan.zember: Fixing broken links and minor grammar errors.2023-04-19T01:12:49Z<p>Fixing broken links and minor grammar errors.</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 01:12, 19 April 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l70" >Line 70:</td>
<td colspan="2" class="diff-lineno">Line 70:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="ho" style="color:red">HO</span>: High-Order logic =====</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="ho" style="color:red">HO</span>: High-Order logic =====</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>High order logic is an extension of [[<del class="diffchange diffchange-inline">#</del>Complexity_Zoo:S#<del class="diffchange diffchange-inline">SO</del>|Second order]], [[<del class="diffchange diffchange-inline">#</del>Complexity_Zoo:F#<del class="diffchange diffchange-inline">FO</del>|First order]] where we add quantification over higher order variables.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>High order logic is an extension of [[Complexity_Zoo:S#<ins class="diffchange diffchange-inline">so</ins>|Second order]], [[Complexity_Zoo:F#<ins class="diffchange diffchange-inline">fo</ins>|First order]] where we add quantification over higher order variables.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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 <del class="diffchange diffchange-inline">constant </del>(first-order <del class="diffchange diffchange-inline">variable</del>) and <del class="diffchange diffchange-inline">relation </del>(second-order variables). The atomic predicates now can be general application of <del class="diffchange diffchange-inline">relation </del>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 <del class="diffchange diffchange-inline"> </del>test of equality between two relations of the same order and arity.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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. <ins class="diffchange diffchange-inline">"</ins>The quantification of formula in HO is over a given order (which is a straightforward extension of SO where we add quantification over <ins class="diffchange diffchange-inline">constants </ins>(first-order <ins class="diffchange diffchange-inline">variables</ins>) and <ins class="diffchange diffchange-inline">relations </ins>(second-order variables<ins class="diffchange diffchange-inline">)</ins>). The atomic predicates now can be general application of <ins class="diffchange diffchange-inline">relations </ins>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><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 <del class="diffchange diffchange-inline">existantial </del>(resp universal) quantifier followed by at most <math>j-1</math> alternation of quantifiers.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><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 <ins class="diffchange diffchange-inline">existential </ins>(resp universal) quantifier followed by at most <math>j-1</math> alternation of quantifiers.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>This class was <del class="diffchange diffchange-inline">define </del>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]].</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>This class was <ins class="diffchange diffchange-inline">defined </ins>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]].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>Brendan.zemberhttps://complexityzoo.net/index.php?title=Complexity_Zoo:H&diff=6761&oldid=prevHuntermonroe: /* HeurP: Heuristic P */2022-05-11T01:33:51Z<p><span dir="auto"><span class="autocomment">HeurP: Heuristic P</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 01:33, 11 May 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l38" >Line 38:</td>
<td colspan="2" class="diff-lineno">Line 38:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The class of distributional problems solvable by a [[Complexity Zoo:P#p|P]] machine. Defined in {{zcite|Imp95}}, though he calls the class HP.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The class of distributional problems solvable by a [[Complexity Zoo:P#p|P]] machine. Defined in {{zcite|Imp95}}, though he calls the class HP.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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<ins class="diffchange diffchange-inline">, for every <math>\delta>0</math></ins>:</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* For every <math>n\in\mathbb{N}</math>, for every <math>x</math> in the support of <math>D<del class="diffchange diffchange-inline"></math>, and for every <math>\delta>0</del></math>, <math>A(x;n,\delta)</math> runs in time bounded by <math>\mathrm{poly}(n/\delta)</math>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* 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>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* <del class="diffchange diffchange-inline">For every <math>\delta>0</math>, </del><math>A(<del class="diffchange diffchange-inline">\cdot</del>;<del class="diffchange diffchange-inline">\cdot</del>,\delta)</math> is a heuristic algorithm for <math>(L,D)</math> whose error probability is bounded by <math>\delta</math>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <math>A(<ins class="diffchange diffchange-inline">x</ins>;<ins class="diffchange diffchange-inline">n</ins>,\delta)</math> is a heuristic algorithm for <math>(L,D)</math> whose error probability is bounded by <math>\delta</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
</table>Huntermonroehttps://complexityzoo.net/index.php?title=Complexity_Zoo:H&diff=6718&oldid=prevJgrochow: /* HalfP: RP With Exactly Half Acceptance */ Added reference to WPP2021-04-27T16:39:30Z<p><span dir="auto"><span class="autocomment">HalfP: RP With Exactly Half Acceptance: </span> Added reference to WPP</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:39, 27 April 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l13" >Line 13:</td>
<td colspan="2" class="diff-lineno">Line 13:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Defined in [[zooref#bb92|[BB92]]], where it was called C<sub>==</sub>P[half] <ins class="diffchange diffchange-inline">(C<sub>==</sub>P being an alternative name for [[Complexity Zoo:W#wpp|WPP]], that apparently didn't catch on or stick)</ins>. 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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
</table>Jgrochowhttps://complexityzoo.net/index.php?title=Complexity_Zoo:H&diff=6716&oldid=prevJgrochow: /* HalfP: RP With Exactly Half Acceptance */ Fixed capitalization on link to BS002021-04-27T16:33:16Z<p><span dir="auto"><span class="autocomment">HalfP: RP With Exactly Half Acceptance: </span> Fixed capitalization on link to BS00</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:33, 27 April 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l13" >Line 13:</td>
<td colspan="2" class="diff-lineno">Line 13:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Defined in [[zooref#bb92|[BB92]]], where it was called C<sub>==</sub>P[half]. The name used here is from [[zooref#<del class="diffchange diffchange-inline">BS00</del>|[BS00]]]. There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Defined in [[zooref#bb92|[BB92]]], where it was called C<sub>==</sub>P[half]. The name used here is from [[zooref#<ins class="diffchange diffchange-inline">bs00</ins>|[BS00]]]. There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
</table>Jgrochowhttps://complexityzoo.net/index.php?title=Complexity_Zoo:H&diff=6679&oldid=prevTooplark at 18:42, 14 November 20202020-11-14T18:42:50Z<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 18:42, 14 November 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l77" >Line 77:</td>
<td colspan="2" class="diff-lineno">Line 77:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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]].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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]].</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===== <span id="hvpzk" style="color:red">HVPZK</span>: Honest-Verifier [[Complexity Zoo:P#pzk|PZK]] =====</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">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).</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Contained in [[Complexity Zoo:P#pp|PP]] [[zooref#bhctv17|[BHCTV17]]].</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">There is an oracle where it is not closed under complement [[zooref#bhctv17|[BHCTV17]]].</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>Tooplarkhttps://complexityzoo.net/index.php?title=Complexity_Zoo:H&diff=47&oldid=prevAdmin: 1 revision: Complexity zoo import.2012-11-18T03:10:30Z<p>1 revision: Complexity zoo import.</p>
<p><b>New page</b></p><div>__NOTOC__<br />
{{CZ-Letter-Menu|H}}<br />
<br />
<br />
===== <span id="halfp" style="color:red">HalfP</span>: RP With Exactly Half Acceptance =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that<br />
<ol><br />
<li>If the answer is 'yes,' exactly 1/2 of computation paths accept.</li><br />
<li>If the answer is 'no,' all computation paths reject.</li><br />
</ol><br />
Significantly, the number of candidate witnesses is restricted to be a power of 2. (This is implicit if they are binary strings.)<br />
<br />
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.<br />
<br />
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.<br />
<br />
----<br />
<br />
===== <span id="heurbpp" style="color:red">HeurBPP</span>: Heuristic [[Complexity Zoo:B#bpp|BPP]] =====<br />
The class of problems for which a 1-1/poly(n) fraction of instances are solvable by a [[Complexity Zoo:B#bpp|BPP]] machine.<br />
<br />
[[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.<br />
<br />
----<br />
===== <span id="heurbptime" style="color:red">HeurBPTIME(f(n))</span>: Heuristic [[Complexity Zoo:B#bptime|BPTIME]](f(n)) =====<br />
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]].<br />
<br />
Thus [[#heurbpp|HeurBPP]] is the union of HeurBPTIME(n<sup>c</sup>) over all c.<br />
<br />
----<br />
<br />
===== <span id="heurdtime" style="color:red">HeurDTIME<sub><math>\delta</math></sub>(f(n))</span>: Heuristic {{zcls|d|dtime}} =====<br />
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}}. <br />
<br />
----<br />
<br />
===== <span id="heurp" style="color:red">HeurP</span>: Heuristic [[Complexity Zoo:P#p|P]] =====<br />
The class of distributional problems solvable by a [[Complexity Zoo:P#p|P]] machine. Defined in {{zcite|Imp95}}, though he calls the class HP.<br />
<br />
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:<br />
* 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>.<br />
* 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>.<br />
<br />
----<br />
<br />
===== <span id="heurpp" style="color:red">HeurPP</span>: Heuristic [[Complexity Zoo:P#p|PP]] =====<br />
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.<br />
<br />
----<br />
<br />
===== <span id="heurntime" style="color:red">HeurNTIME<sub><math>\delta</math></sub></span>(f(n)): Heuristic {{zcls|n|ntime}} =====<br />
Defined as [[#heurdtime|Heur<sub><math>\delta</math></sub>DTIME]], but for non-deterministic heuristic algorithms.<br />
<br />
{{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}}.<br />
----<br />
<br />
===== <span id="hkp" style="color:red">H<sub>k</sub>P</span>: High Hierarchy In [[Complexity Zoo:N#np|NP]] =====<br />
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.<br />
<br />
For all k, H<sub>k</sub> is contained in H<sub>k+1</sub>.<br />
<br />
H<sub>0</sub> consists exactly of the problems complete for [[Complexity Zoo:N#np|NP]] under Cook reductions.<br />
<br />
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]]].<br />
<br />
Defined in [[zooref#sch83|[Sch83]]].<br />
<br />
See also [[Complexity Zoo:L#lkp|L<sub>k</sub>P]].<br />
<br />
----<br />
===== <span id="ho" style="color:red">HO</span>: High-Order logic =====<br />
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.<br />
<br />
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.<br />
<br />
<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.<br />
<br />
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]].<br />
----<br />
<br />
===== <span id="hvszk" style="color:red">HVSZK</span>: Honest-Verifier [[Complexity Zoo:S#szk|SZK]] =====<br />
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).<br />
<br />
Equals [[Complexity Zoo:S#szk|SZK]] [[zooref#oka96|[Oka96]]].</div>Admin