A Promise Class at Least as Hard as the Polynomial Hierarchy
J org Rothe · 1994
In this paper, an open problem raised by Toda and Ogiwara is reformulated in the context of promise problems to make precise its very nature---thereby answering it partially---which, by intuition, is due to the promise in the definition of SPP. In particular, it is shown that the polynomial hierarchy is contained in a promise class that naturally corresponds to the class BP \cdot SPP (even though for this class itself, unfortunately, the original problem remains unsolved). Furthermore, some properties of several related classes defined via operators are studied.