<p>Consider a PSPACE-complete problem (e.g., TQBF).</p>

<ol>
<li><p>Is there a sub-problem in BPP, that is not known to be in P?</p></li>
<li><p>Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e., not completely contrived languages)?</p></li>
</ol>

<p>By "sub-problem" I mean a promise problem whose yes/no instances are respectively contained in those of the original language.</p>

<p>For example, asking the same question with NP instead of BPP, we can take the problem <span class="math-container">$\exists$</span>TQBF (where the promise is that all the quantifiers are existential), namely SAT.</p>

<p>CLARIFICATION:
I'm interested in finding <em>some</em> PSPACE-complete problem that has such a BPP sub-problem. It would be good if the PSPACE-complete problem is a "natural" one, such as TQBF, but I'm open to suggestions.</p>

CC BY-SA 4.0
2019-12-22T19:43:34.553Z
Are you asking whether we can come up with a PSPACE-complete problem and a set of instances that are in BPP but not known to be in P?  Or are you asking specifically about TQBF?  Or are you asking for a general procedure that, given a PSPACE-complete problem, finds a set of instances that are in BPP but not known to be in P?  I'm not entirely clear on what you are asking.
D.W.
CC BY-SA 4.0
2019-12-22T20:22:31.733Z
I'm mainly interested in starting with a specific PSPACE complete problem (TQBF, for the sake of the example, but I'm open to suggestions), and finding a set of instances that are in BPP but not known to be in P. What you suggest might also be interesting -- "extending" a BPP problem to become PSPACE-complete, but would probably be less natural. As for a general procedure: I'm not asking for an algorithm, but if there is such a subproblem for TQBF, perhaps there is some general technique involved.
Shaull
<complexity-classes><randomness>
BPP fragment of a PSPACE complete problem
Shaull
# BPP fragment of a PSPACE complete problem

(Asked by: username_0 on 2019-12-22)

Consider a PSPACE-complete problem (e.g., TQBF).

1. Is there a sub-problem in BPP, that is not known to be in P?
2. Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e., not completely contrived languages)?

By "sub-problem" I mean a promise problem whose yes/no instances are respectively contained in those of the original language.

For example, asking the same question with NP instead of BPP, we can take the problem $\exists$TQBF (where the promise is that all the quantifiers are existential), namely SAT.

CLARIFICATION:
I'm interested in finding *some* PSPACE-complete problem that has such a BPP sub-problem. It would be good if the PSPACE-complete problem is a "natural" one, such as TQBF, but I'm open to suggestions.

**Tags:** complexity-classes, randomness

> **Comments:**
> **username_1**: Are you asking whether we can come up with a PSPACE-complete problem and a set of instances that are in BPP but not known to be in P?  Or are you asking specifically about TQBF?  Or are you asking for a general procedure that, given a PSPACE-complete problem, finds a set of instances that are in BPP but not known to be in P?  I'm not entirely clear on what you are asking.  
> **username_0**: I'm mainly interested in starting with a specific PSPACE complete problem (TQBF, for the sake of the example, but I'm open to suggestions), and finding a set of instances that are in BPP but not known to be in P. What you suggest might also be interesting -- "extending" a BPP problem to become PSPACE-complete, but would probably be less natural. As for a general procedure: I'm not asking for an algorithm, but if there is such a subproblem for TQBF, perhaps there is some general technique involved.  

---

## 0 answers

