Abstract
Via competing provers, we show that if a language
A is self-reducible and has polynomial-size circuits then
S
2
A
=
S
2
. Building on this, we strengthen the Kämper–AFK theorem, namely, we prove that if NP
⊆
(NP
∩
coNP)/poly then the polynomial hierarchy collapses to
S
2
NP
∩
coNP
. We also strengthen Yap’s theorem, namely, we prove that if NP
⊆
coNP/poly then the polynomial hierarchy collapses to
S
2
NP
. Under the same assumptions, the best previously known collapses were to ZPP
NP and
ZPP
NP
NP
, respectively ([SIAM Journal on Computing 28 (1) (1998) 311; Journal of Computer and System Sciences 52 (3) (1996) 421], building on [Proceedings of the 12th ACM Symposium on Theory of Computing, ACM Press, New York, 1980, pp. 302–309; Journal of Computer and System Sciences 39 (1989) 21; Theoretical Computer Science 85 (2) (1991) 305; Theoretical Computer Science 26 (3) (1983) 287]). It is known that S
2
⊆
ZPP
NP [Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 2001, pp. 620–629]. That result and its relativized version show that our new collapses indeed improve the previously known results. The Kämper–AFK theorem and Yap’s theorem are used in the literature as bridges in a variety of results—ranging from the study of unique solutions to issues of approximation—and so our results implicitly strengthen those results.
