<p>In analogy to <strong>BPP</strong>, I define a class <strong>XYZ</strong> (maybe it already has a name) as follows. For every language <span class="math-container">$L$</span> in <strong>XYZ</strong>, there is an algorithm <span class="math-container">$M$</span>, such that:</p>
<ol>
<li><span class="math-container">$M$</span> runs in polynomial time on the size of its input;</li>
<li><span class="math-container">$M$</span> returns either 0, 1, or 'I DO NOT KNOW' (at variance with <strong>BPP</strong>!);</li>
<li>the probability of getting either 0 or 1 does not vanish;</li>
<li>for all <span class="math-container">$x$</span> in <span class="math-container">$L$</span>, the probability of getting 1 from <span class="math-container">$M$</span> when it does <strong>not</strong> return 'I DO NOT KNOW' is greater than or equal to 2/3</li>
<li>for all <span class="math-container">$x$</span> not in <span class="math-container">$L$</span>, the probability of getting 1 from <span class="math-container">$M$</span> when it does <strong>not</strong> return 'I DO NOT KNOW' is less than or equal to 1/3</li>
</ol>
<p>To better clarify: the probabilities mentioned in points 4 and 5 are calculated on the 0 or 1 outputs, thus neglecting the 'I DO NOT KNOW' values. E.g., for a given algorithm and a given <span class="math-container">$x$</span>, if the algorithm outputs 0 with overall probability 2%, 1 with overall probability 6%, and 'I DO NOT KNOW' with overall probability 92%, the probability mentioned in points 4 and 5 is 75%, i.e. 6%/(2%+6%).</p>
<p>I think that <strong>BPP</strong> <span class="math-container">$\subseteq$</span> <strong>XYZ</strong> <span class="math-container">$\subseteq$</span><strong>PP</strong>, i.e. the class I am asking about is between <strong>BPP</strong> and <strong>PP</strong>:</p>
<p><strong>BPP</strong><span class="math-container">$\subseteq$</span><strong>XYZ</strong> because the algorithm required in <strong>BPP</strong> is also a valid algorithm for <strong>XYZ</strong>, even if it always returns 0 or 1 (and never 'I DO NOT KNOW')</p>
<p><strong>XYZ</strong><span class="math-container">$\subseteq$</span><strong>PP</strong> because we can extend any algorithm of <strong>XYZ</strong> to a valid algorithm for <strong>PP</strong> by randomly returning 0 or 1 when 'I DO NOT KNOW' is returned in first place</p>
<p>I also think that <strong>NP</strong> <span class="math-container">$\subseteq$</span> <strong>XYZ</strong>; the proof follows the proof of <strong>NP</strong> <span class="math-container">$\subseteq$</span> <strong>PP</strong>. So <strong>XYZ</strong> is likely larger than <strong>BPP</strong>. However, I do not understand if <strong>XYZ</strong> is equal to <strong>PP</strong>. Informally, I do not see reasons why the algorithm requested by <strong>PP</strong> can be extended to a lazy algorithm required by <strong>XYZ</strong> increasing its success rate.</p>
<p>Is this class known in literature? Does it have a name? Is it studied? Is it really different from <strong>PP</strong>? Any comment is welcome.</p>

CC BY-SA 4.0
2024-08-12T16:54:00.377Z
This is in the polynomial hierarchy ($\mathrm{BPP^{NP}}$, I guess) by approximate counting: approximate the number of random sequences that make $M$ return $1$, resp. $0$, within a factor of, say, $4/3$, and return whichever is larger. Thus, it is most likely smaller than PP.
Emil Jeřábek
CC BY-SA 4.0
2024-08-13T08:14:39.153Z
It is very interesting, I think that it would be valuable to expand this comment into a full answer. I know that this site is for professionals, but this discussion is not trivial for me and a longer explanation could help other users, in view of multidisciplinarity.
Doriano Brogioli
CC BY-SA 4.0
2024-08-13T08:54:38.910Z
Well, I can't do that now as I'm on vacation.
Emil Jeřábek
CC BY-SA 4.0
2024-08-13T09:21:04.923Z
Isn't it BPP_path or sometimes called PostBPP? Conditioning on not "I don't know" seems like a postselection.
Hhan
CC BY-SA 4.0
2024-08-13T12:35:28.563Z
Yes, it is! It matches with the definition of PostBPP in https://arxiv.org/abs/quant-ph/0606140v4. The paper also shows that PostBPP is included in BPP^NP and explains the connection with the counting (so, we do not have to disturb the vacations of Emil Jerabek!) Thanks again to both.
Doriano Brogioli
CC BY-SA 4.0
2024-08-14T01:29:34.160Z
Yes, it's good to see the complexity zoo for a quick summary: https://complexityzoo.net/Complexity_Zoo:B#bpppath
Also, note that the quantum analog PostBQP is *equal* to PP, as shown by Aaronson.
Hhan
CC BY-SA 4.0
2024-08-19T12:09:20.510Z
Then PostBQP strictly includes PostBPP, unless PH collapses. Is the relation between PostBPP and BQP known? Based on the conjecture that BQP is not included in PH, we can say that BQP is not included in PostBPP as well. Is there a proof based on more robust conjectures (like PH does not collapse)?
Doriano Brogioli
<cc.complexity-theory><complexity-classes>
Is this class between BPP and PP?
Doriano Brogioli
# Is this class between BPP and PP?

(Asked by: username_0 on 2024-08-12)

In analogy to **BPP**, I define a class **XYZ** (maybe it already has a name) as follows. For every language $L$ in **XYZ**, there is an algorithm $M$, such that:

1. $M$ runs in polynomial time on the size of its input;
2. $M$ returns either 0, 1, or 'I DO NOT KNOW' (at variance with **BPP**!);
3. the probability of getting either 0 or 1 does not vanish;
4. for all $x$ in $L$, the probability of getting 1 from $M$ when it does **not** return 'I DO NOT KNOW' is greater than or equal to 2/3
5. for all $x$ not in $L$, the probability of getting 1 from $M$ when it does **not** return 'I DO NOT KNOW' is less than or equal to 1/3

To better clarify: the probabilities mentioned in points 4 and 5 are calculated on the 0 or 1 outputs, thus neglecting the 'I DO NOT KNOW' values. E.g., for a given algorithm and a given $x$, if the algorithm outputs 0 with overall probability 2%, 1 with overall probability 6%, and 'I DO NOT KNOW' with overall probability 92%, the probability mentioned in points 4 and 5 is 75%, i.e. 6%/(2%+6%).

I think that **BPP** $\subseteq$ **XYZ** $\subseteq$**PP**, i.e. the class I am asking about is between **BPP** and **PP**:

**BPP**$\subseteq$**XYZ** because the algorithm required in **BPP** is also a valid algorithm for **XYZ**, even if it always returns 0 or 1 (and never 'I DO NOT KNOW')

**XYZ**$\subseteq$**PP** because we can extend any algorithm of **XYZ** to a valid algorithm for **PP** by randomly returning 0 or 1 when 'I DO NOT KNOW' is returned in first place

I also think that **NP** $\subseteq$ **XYZ**; the proof follows the proof of **NP** $\subseteq$ **PP**. So **XYZ** is likely larger than **BPP**. However, I do not understand if **XYZ** is equal to **PP**. Informally, I do not see reasons why the algorithm requested by **PP** can be extended to a lazy algorithm required by **XYZ** increasing its success rate.

Is this class known in literature? Does it have a name? Is it studied? Is it really different from **PP**? Any comment is welcome.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: This is in the polynomial hierarchy ($\mathrm{BPP^{NP}}$, I guess) by approximate counting: approximate the number of random sequences that make $M$ return $1$, resp. $0$, within a factor of, say, $4/3$, and return whichever is larger. Thus, it is most likely smaller than PP.  
> **username_0**: It is very interesting, I think that it would be valuable to expand this comment into a full answer. I know that this site is for professionals, but this discussion is not trivial for me and a longer explanation could help other users, in view of multidisciplinarity.  
> **username_1**: Well, I can't do that now as I'm on vacation.  
> **username_2**: Isn't it BPP_path or sometimes called PostBPP? Conditioning on not "I don't know" seems like a postselection.  
> **username_0**: Yes, it is! It matches with the definition of PostBPP in https://arxiv.org/abs/quant-ph/0606140v4. The paper also shows that PostBPP is included in BPP^NP and explains the connection with the counting (so, we do not have to disturb the vacations of Emil Jerabek!) Thanks again to both.  
> **username_2**: Yes, it's good to see the complexity zoo for a quick summary: https://complexityzoo.net/Complexity_Zoo:B#bpppath Also, note that the quantum analog PostBQP is *equal* to PP, as shown by Aaronson.  
> **username_0**: Then PostBQP strictly includes PostBPP, unless PH collapses. Is the relation between PostBPP and BQP known? Based on the conjecture that BQP is not included in PH, we can say that BQP is not included in PostBPP as well. Is there a proof based on more robust conjectures (like PH does not collapse)?  

---

## 0 answers

