Fixed-Polynomial Circuit Lower Bounds for $\oplus P$, Uniform $MA$, $P^{NP}$, and $NP$

A 2009 paper of Fortnow, Santhanam, and Williams fixed the landscape of fixed-polynomial circuit lower bounds — bounds of the form $n^k$ for fixed $k$ — by proving that the question for $NP$ is equivalent to the question for every bounded-query version of $P^{NP}$, by exhibiting an oracle relative to which $\oplus P$ has quadratic-size circuits while the collapse used to prove lower bounds for $PP$ still holds, and by asking whether such lower bounds can be pushed to $\oplus P$, uniform $MA$, $P^{NP}$, or $NP$. No fixed-polynomial circuit lower bound is known for any of $\oplus P$, uniform (advice-free) $MA$, $P^{NP}$, or $NP$. The open core is the source paper's own question, together with its two auxiliary structural problems: whether $NP\subseteq SIZE(n^k)$ implies $P^{NP}\subseteq SIZE(n^{k'})$, and whether an Aaronson–Wigderson-style algebrization barrier exists for $\oplus P$.

Background

Fix the standard Boolean circuit model (fan-in-two gates). A language $L$ is in $SIZE(n^k)$ if for every input length $n$ there is a circuit family of $O(n^k)$ gates computing $L$ at that length; the family need not be efficiently constructible, which is what makes circuit lower bounds hard. A fixed-polynomial circuit lower bound for a complexity class $\mathcal{C}$ is a proof that $\mathcal{C}\not\subseteq SIZE(n^k)$ for every fixed constant $k$. Such bounds are the first quantitative step toward super-polynomial separations such as $NP\not\subseteq P/\mathrm{poly}$ — where $P/\mathrm{poly}=\bigcup_k SIZE(n^k)$ is the class of all languages with polynomial-size circuit families — and through the hardness-versus-randomness connection (the principle that computational hardness yields pseudorandom generators, and hence deterministic simulations of randomized algorithms) they underpin derandomization. Kannan (1982) proved $\Sigma_2^P\not\subseteq SIZE(n^k)$ for all $k$, where $\Sigma_2^P$ is the second level of the polynomial hierarchy (nondeterministic polynomial time augmented by an $NP$ oracle). This was strengthened over two decades; the smallest standard class reached is $S_2^P$ (Cai, 2007, via the containment $S_2^P\subseteq ZPP^{NP}$), where $S_2^P$ is the symmetric-certificates class in which polynomial-size yes-certificates and no-certificates compete under a polynomial-time verifier, and $ZPP^{NP}$ is zero-error randomized polynomial time with an $NP$ oracle.

Two later lower bounds use arguments that do not relativize. An oracle is an external black-box set that machines may query; a proof relativizes if it remains valid relative to every oracle. Vinodchandran (2005) proved $PP\not\subseteq SIZE(n^k)$ for all $k$, where $PP$ is the counting class of languages accepted by nondeterministic polynomial-time machines when a majority of computation paths accept. Santhanam (2007) proved the analogous bound for $MA/1$: Merlin–Arthur protocols — a nondeterministic prover's message followed by a randomized polynomial-time verification — equipped with a single nonuniform advice bit (the conference version phrases the result for the promise version of $MA$, where correctness is required only on inputs satisfying a promised condition). Both proofs exploit interactive-proof collapses such as $P^{PP}\subseteq MA$, descendants of the characterizations $IP=PSPACE$ (languages with membership proofs verified by a randomized polynomial-time machine interacting with an all-powerful prover are exactly those decidable in polynomial space) and $MIP=NEXP$ (the same with multiple non-communicating provers captures nondeterministic exponential time), and they evade both relativization and the natural-proofs barrier (the Razborov–Rudich theorem that a broad class of efficient combinatorial lower-bound arguments must fail under standard cryptographic assumptions).

Below these classes the frontier is untouched. The class $\oplus P$ (Parity-$P$) consists of languages accepted by nondeterministic polynomial-time machines when the parity, rather than the majority, of accepting paths is counted. Although $\oplus P\subseteq PP$, lower bounds never transfer from a class to a subclass, so Vinodchandran's result says nothing about $\oplus P$; likewise uniform $MA$ (no advice) and $NP$ itself lie inside $PP$ and $\Sigma_2^P$, and $P^{NP}$ — polynomial time with polynomially many adaptive queries to an $NP$ oracle, the class $\Delta_2^P$ — lies inside $\Sigma_2^P$, classes with known bounds, without inheriting anything.

The algebrization barrier of Aaronson and Wigderson (2009) explains the impasse. A proof algebrizes if it remains valid relative to every oracle $A$ when the machines involved may additionally query $\widetilde{A}$, the multilinear extension of $A$ (the unique multilinear polynomial over a finite field that agrees with $A$ on Boolean inputs). Essentially all known structural complexity results algebrize, while fixed-polynomial lower bounds for $NP$ — and weaker targets — provably cannot be established by algebrizing methods.

Fortnow, Santhanam, and Williams (CCC 2009) mapped the terrain beyond this barrier. They proved: $NP\subseteq SIZE(n^k)$ for some $k$ if and only if $P^{NP[n^q]}\subseteq SIZE(n^{k'})$ for some $k'$ (for any fixed $q$, taking $k'=qk^2$ suffices), where $P^{NP[n^q]}$ is polynomial time with at most $n^q$ adaptive $NP$-oracle queries — so the lower-bound question for $NP$ is equivalent to that for every bounded-query version of $P^{NP}$; that a strong derandomization of linear-time Merlin–Arthur games ($\mathrm{MATIME}(n)\subseteq\mathrm{NTIME}(n^d)$ for some $d$) would imply $P^{NP}\not\subseteq SIZE(n^k)$; and, by analyzing an oracle of Beigel–Buhrman–Fortnow relative to which $P=\oplus P$ and $NP=EXP$, that there is an oracle relative to which $P^{\oplus P}\subseteq MA$ and $\oplus P\subseteq SIZE(n^2)$ (Theorem 16, whose oracle bound $\oplus P\subseteq SIZE(n^k)$ for some constant $k$ is refined to $SIZE(n^2)$, combined with Corollary 18, which adds the collapse $P^{\oplus P}\subseteq MA$). Since the implication $P^{PP}\subseteq MA\Rightarrow PP\not\subseteq SIZE(n^k)$ holds relative to every oracle (Corollary 17), but its $\oplus P$ analogue fails relative to this oracle, any proof of even $\oplus P\not\subseteq SIZE(n^2)$ requires nonrelativizing techniques beyond those used for $PP$. They also observed, via an oracle of Buhrman–Fenner–Fortnow–Torenvliet relative to which $NEXP\subseteq P^{NP}\cap P/\mathrm{poly}$, that proving $NP\subseteq SIZE(n^k)\Rightarrow P^{NP}\subseteq SIZE(n^{k'})$ would require nonrelativizing techniques. Their open questions — lower bounds for $\oplus P$, uniform $MA$, $P^{NP}$, and $NP$, an algebrization-barrier analogue of Theorem 16 for $\oplus P$, and the size-transfer implication — remain open.

Problem Statement

Overarching question (Fortnow–Santhanam–Williams, CCC 2009): can fixed-polynomial circuit lower bounds be proved for any of the classes $\oplus P$, uniform $MA$, $P^{NP}$, or $NP$ — or can one prove that algebrizing techniques cannot do so? A resolution establishes at least one of the following; each is an independently checkable facet of the same frontier, and all lower-bound claims are unconditional statements about general Boolean circuits.

(1) Prove $\oplus P\not\subseteq SIZE(n^k)$ for every fixed $k$; even the quadratic target $\oplus P\not\subseteq SIZE(n^2)$ is open and, by Theorem 16 with Corollaries 17–18 of the source paper, requires nonrelativizing techniques beyond those that suffice for $PP$.

(2) Prove $MA\not\subseteq SIZE(n^k)$ for every fixed $k$ for the uniform (advice-free) Merlin–Arthur class, eliminating the advice bit from Santhanam's $MA/1$ bound.

(3) Prove $P^{NP}\not\subseteq SIZE(n^k)$ for every fixed $k$ — the frontier problem so named by Chen–McKay–Murray–Williams (2019), a necessary intermediate step toward $NP\not\subseteq P/\mathrm{poly}$.

(4) Prove $NP\not\subseteq SIZE(n^k)$ for every fixed $k$; this would also separate $NEXP$ (nondeterministic exponential time) from $BPP$ (bounded-error randomized polynomial time) and is known (Aaronson–Wigderson) to require non-algebrizing techniques.

(5) Settle the size-transfer question: does $NP\subseteq SIZE(n^k)$ for some $k$ imply $P^{NP}\subseteq SIZE(n^{k'})$ for some $k'$ depending only on $k$? (Known for $n^q$ adaptive queries with $k'=qk^2$ by Theorem 10 of the source; open — and necessarily nonrelativizing — for full $P^{NP}$.)

(6) Construct, in the Aaronson–Wigderson algebrization framework, an oracle $A$ and its multilinear extension $\widetilde{A}$ relative to which $\oplus P$ has fixed-polynomial-size circuits while the interactive-proof-based collapses used in the $PP$ lower bound still hold — the algebrization barrier for $\oplus P$ that the source paper explicitly poses as an interesting open problem. An analogous barrier for uniform $MA$ would answer the question Chen–Hu–Ren re-posed in 2025.

References

1. Lance Fortnow, Rahul Santhanam, Ryan Williams. Fixed-Polynomial Size Circuit Bounds. In 24th IEEE Conference on Computational Complexity (CCC 2009), pp. 19–26. DOI: 10.1109/CCC.2009.21. https://doi.org/10.1109/CCC.2009.21 (author PDF at https://www.cs.cmu.edu/~ryanw/circuit.pdf)
2. Ravi Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control 55(1–3):40–56, 1982. DOI: 10.1016/S0019-9958(82)90382-5. https://doi.org/10.1016/S0019-9958(82)90382-5
3. N. V. Vinodchandran. A note on the circuit complexity of PP. Theoretical Computer Science 347(1–2):415–418, 2005. DOI: 10.1016/j.tcs.2005.07.032. https://doi.org/10.1016/j.tcs.2005.07.032
4. Jin-Yi Cai. $S_2^P\subseteq ZPP^{NP}$. Journal of Computer and System Sciences 73(1):25–35, 2007. DOI: 10.1016/j.jcss.2003.07.015. https://doi.org/10.1016/j.jcss.2003.07.015
5. Rahul Santhanam. Circuit lower bounds for Merlin-Arthur classes. In Proceedings of 39th STOC, pp. 275–283, 2007. DOI: 10.1145/1250790.1250832. https://doi.org/10.1145/1250790.1250832 (ECCC TR07-005: https://eccc.weizmann.ac.il/report/2007/005/)
6. Scott Aaronson, Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory 1(1):1–54, 2009. DOI: 10.1145/1490270.1490272. https://doi.org/10.1145/1490270.1490272
7. Richard Beigel, Harry Buhrman, Lance Fortnow. NP might not be as easy as detecting unique solutions. In Proceedings of 30th STOC, pp. 203–208, 1998. DOI: 10.1145/276698.276737. https://doi.org/10.1145/276698.276737
8. Harry Buhrman, Steve Fenner, Lance Fortnow, Leen Torenvliet. Two oracles that force a big crunch. Computational Complexity 10(2):93–116, 2001. DOI: 10.1007/s00037-001-8190-2. https://doi.org/10.1007/s00037-001-8190-2
9. Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova. An axiomatic approach to algebrization. In Proceedings of 41st STOC, pp. 695–704, 2009. DOI: 10.1145/1536414.1536509. https://doi.org/10.1145/1536414.1536509
10. Alexander Knop. Circuit Lower Bounds for Heuristic MA. ECCC Technical Report TR13-037, 2013 (revision 2014). https://eccc.weizmann.ac.il/report/2013/037/
11. Hervé Fournier, Sylvain Perifel, Rémi de Joannis de Verclos. On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant. Information and Computation 240:31–41, 2015. DOI: 10.1016/j.ic.2014.09.006. https://arxiv.org/abs/1304.5910
12. Cody D. Murray, R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp. 890–901. DOI: 10.1145/3188745.3188910. https://doi.org/10.1145/3188745.3188910
13. Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. In 34th Computational Complexity Conference (CCC 2019), LIPIcs vol. 137, Article 30. DOI: 10.4230/LIPIcs.CCC.2019.30. https://doi.org/10.4230/LIPIcs.CCC.2019.30
14. Shuichi Hirahara, Zhenjian Lu, Hanlin Ren. Bounded Relativization. In 38th Computational Complexity Conference (CCC 2023), LIPIcs vol. 264, Article 6. DOI: 10.4230/LIPIcs.CCC.2023.6. https://doi.org/10.4230/LIPIcs.CCC.2023.6
15. Joshua Cook, Dana Moshkovitz. Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE. In APPROX/RANDOM 2023, LIPIcs vol. 275, Article 55, pp. 55:1–55:22. DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.55. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.55
16. Justin Yirka. Even quantum advice is unlikely to solve PP. Theory of Computing 21(7), 2025. DOI: 10.4086/toc.2025.v021a007. arXiv:2403.09994. https://arxiv.org/abs/2403.09994
17. Karthik Gajulapalli, Zeyong Li, Ilya Volkovich. Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024), LIPIcs vol. 323, Article 23, pp. 23:1–23:19. DOI: 10.4230/LIPIcs.FSTTCS.2024.23. arXiv:2510.15268. https://arxiv.org/abs/2510.15268
18. Lijie Chen, Jiatu Li, Jingxun Liang. Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin. ECCC Technical Report TR24-182, 2024. https://eccc.weizmann.ac.il/report/2024/182/
19. Lijie Chen, Yang Hu, Hanlin Ren. New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String. arXiv:2511.14038, 2025 (ITCS 2026); also ECCC TR25-184. https://arxiv.org/abs/2511.14038
20. Hanlin Ren, R. Ryan Williams. Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries. ECCC Technical Report TR26-118, 2026. https://eccc.weizmann.ac.il/report/2026/118/