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.

  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. Dec 22 '19 at 19:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Shaull Dec 22 '19 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.