Proved
Established implication or scoped theorem in cited mathematics ↗
Ryan Williams · Non-uniform ACC circuit lower bounds · Abstract and main theorem, p. 1 →
Observed Oct 10, 2026
Theorem · version 1
NEXP has no polynomial-size ACC circuits
Earlier version 1. View current version 2 →
Statement
NEXP is not contained in nonuniform polynomial-size ACC.
Assumptions
- Constant circuit depth; unbounded fan-in AND, OR, NOT and MOD_m gates for a fixed integer m > 1.
Scope
Nondeterministic exponential time versus restricted nonuniform circuits; not an NP lower bound against unrestricted circuits.
Evidence
Source reports
Connections
In this problem · publication v7 · Selected context
P versus NP →
Restricted-model result · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Scope: NEXP is outside nonuniform polynomial-size ACC: constant-depth circuits with fixed-modulus counting gates.
This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.
Relationship not independently reviewed. This concerns its use in this problem.
Sources
Ryan Williams · Non-uniform ACC circuit lower bounds →
- Abstract and main theorem, p. 1 → · Original passage ↗
Recorded wording
NEXP is not contained in nonuniform polynomial-size ACC.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Ryan Williams · Published · Publication date 2011
Published author exposition or original paper.
Ryan Williams · Non-uniform ACC circuit lower bounds — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: CCC-2011-author-version. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Ryan Williams · Non-uniform ACC circuit lower bounds — proof text: CCC-2011-author-version. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-nexp-acc
- Statement version
- 1
- SHA-256
- 7744045084750b0ef2f27c491e6edf154f5cdc16020414eedb1e79a1b1bf3a22