# BPP fragment of a PSPACE complete problem

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.

• 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. Dec 22 '19 at 19:43
• 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 Dec 22 '19 at 20:22