Super-polynomial ACC⁰ lower bounds for a language in NP: extending Murray–Williams beyond NQP

Known. Williams (CCC 2011; J. ACM 2014, doi:10.1145/2559903) proved $\mathsf{NEXP}\not\subset\mathsf{ACC}^0$, using an algorithm solving ACC⁰-SAT in time $2^{n-n^{\delta}}$ and the nondeterministic time hierarchy. Murray and Williams (STOC 2018) proved by an "easy witness" lemma showing that NQP languages have witnesses that are circuits of small size; Chen (ECCC TR19-031; FOCS 2019) proved that NQP is average-case hard for ACC⁰. Chen (ECCC TR22-183) gave a derandomisation-centred proof of , fixed-polynomial ACC⁰ lower bounds for MA-type classes with ACC⁰ verifiers, and improved the ACC⁰ size lower bound for NEXP from sub-third-exponential to sub-half-exponential. Chen, Hirahara and Ren (2024) and Li (2024) proved symmetric-exponential-time lower bounds, which concern a different class, not ACC⁰.

A lower bound for ACC⁰ in NP would significantly sharpen understanding of the limits of constant-depth circuits with modular counting, which model parallel and algebraic computation. It would give a template for turning faster algorithms into lower bounds for other classes. There is no direct practical application.

A proof, accepted by complexity theorists, that some language in $\mathsf{NP}$ requires super-polynomial-size $\mathsf{ACC}^0$ circuits. The same for a class strictly between $\mathsf{NP}$ and $\mathsf{N}\mathsf{Q}\mathsf{P}$, or for , is significant partial progress.