Proved
Established implication or scoped theorem in cited mathematics ↗
Ren–Williams · Near-maximum circuit lower bounds · Theorem 1.1, p. 2 →
Observed Oct 10, 2026
Theorem · version 2
Near-maximum general circuit lower bound in an oracle class
Statement
There exists a function in E^{prMA}/1 requiring Boolean circuits of size Ω(2^n/n).
Assumptions
- Deterministic exponential time with a promise-MA oracle; one bit of advice; the algorithm queries promised instances on the correct advice bit.
Scope
An oracle/advice class above the target NP; no general NP separation follows.
Evidence
Source reports
Connections
In this problem · publication v13 · 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: An E^{prMA}/1 function needs Ω(2^n/n) general Boolean circuit size, retaining its promise oracle and one advice bit.
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.
In this problem · publication v14
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: An E^{prMA}/1 function needs Ω(2^n/n) general Boolean circuit size, retaining its promise oracle and one advice bit.
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
Ren–Williams · Near-maximum circuit lower bounds →
- Theorem 1.1, p. 2 → · Original passage ↗
Recorded wording
There exists a function in E^{prMA}/1 requiring Boolean circuits of size Ω(2^n/n).
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Hanlin Ren · Ryan Williams · Preprint · Publication date Jul 10, 2026
Source-reported preprint/project; independent mathematical assessment pending.
Ren–Williams · Near-maximum circuit lower bounds — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: arXiv-2607.09963v1. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Ren–Williams · Near-maximum circuit lower bounds — proof text: arXiv-2607.09963v1. 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-near-maximum-2026
- Statement version
- 2
- SHA-256
- 001d650b3e87272e4b0f70dbb85937d4d09fffa9d300f00daf0720786e89788b