Abstract and main theorem, p. 1
NEXP is not contained in nonuniform polynomial-size ACC.
Passage details
Passage ID: pnp-entry-nexp-acc:v1
Source item: nexp-acc
Source record: pnp-williams@CCC-2011-author-version
Ryan Williams · Non-uniform ACC circuit lower bounds
PublishedPublication date 2011
Open paper ↗Overview
The precise statements and locators cited in this P versus NP research record.
Published author exposition or original paper.
1 cited passage ↓1 problem ↓Record CCC-2011-author-version ↓
Passages
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
Used in
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
P versus NP →
Problem publication v14
NEXP has no polynomial-size ACC circuits →
Source assessment
Proved
Established implication or scoped theorem in cited mathematics
Nondeterministic exponential time versus restricted nonuniform circuits; not an NP lower bound against unrestricted circuits.
Observed Oct 10, 2026
Problem context · 3 citations
Further reading
Read the mathematical argument; inspect its Claim for assessment and scope.
Files
Linked manuscripts, code and data. External proof reports, statement correspondence and OpenMath execution are separate checks.
Ryan Williams · Non-uniform ACC circuit lower bounds — proof text ↗
Manuscript / exposition · external
External source text. Its mathematical claims and independent OpenMath review are assessed separately.
Resource revision: CCC-2011-author-version
File checksum
SHA-256 for this linked file. A matching checksum identifies the same bytes; it does not assess the mathematics.
91a09d1ea06fab97e26a791010fd4a902d4be30675998e5bd5e9f8bf68389f80Credits
Recorded authorship
Ryan Williams
AI involvement not reported
AI involvement is not reported by this cited source; this is not a claim of its absence.
Versions
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
- CCC-2011-author-version · selectedObserved Oct 10, 2026 · used in current publications
Ryan Williams · Non-uniform ACC circuit lower bounds
Record details
- Source ID
- pnp-williams
- Record ID
- pnp-williams@CCC-2011-author-version
- Recorded title
- Ryan Williams · Non-uniform ACC circuit lower bounds
- Revision
- CCC-2011-author-version
- Observed
- Oct 10, 2026
- Source updated
- Not recorded
- Content SHA-256
- 91a09d1ea06fab97e26a791010fd4a902d4be30675998e5bd5e9f8bf68389f80
- Update method
- Manual primary-source check; changes require a new source version and staff publication.
- Identifier policy
- Source URL and exact theorem/section locator; no inferred identity merge.
- Check interval
- 30 days
- Rights
- metadata-link
- License
- Full-text redistribution rights not asserted
Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Source terms ↗