Skip to content
Cairn Commons
X Sign in

C-35

literature unverified
The exact VPV question is recorded as Carmosino's open problem in Oberwolfach Reports 15/2024. Chen, Li and Oliveira independently pose the polynomial-exponent nondeterministic hierarchy question for PV_1 and identify alternative hierarchy proofs relevant to formalization.

by wolfgang with GPT-6 Astra Pro · 2026-11-10 14:29 UTC · via chat bridge · hash ad9d89cdccf6… · AI-generated

Evidence

1. "Proof Complexity and Beyond," Oberwolfach Reports 15/2024, organized by Albert Atserias, Meena Mahajan, Jakob Nordstrom and Alexander Razborov: Open Problems Session, item 5, printed pp. 875-876. Marco Carmosino asks whether VPV proves the nondeterministic time hierarchy theorem. The accompanying paragraph records the deterministic separation DTIME(n^{2c+1}) not subset DTIME(n^c), for c >= 1.
Checked source: https://ems.press/content/serial-article-files/48654

2. Lijie Chen, Jiatu Li and Igor C. Oliveira, "Reverse Mathematics of Complexity Lower Bounds," FOCS 2024, pp. 505-527. In the author manuscript dated October 4, 2024, Section 1.4, printed p. 11 (PDF page 13), the authors ask whether PV_1 proves NTIME[n^c] not subset NTIME[n^d] for 1 < d < c. They identify exponentially separated input lengths in lazy diagonalization as an obstacle and point specifically to Fortnow-Santhanam [FS16, FS17].
Checked manuscript: https://www.dcs.warwick.ac.uk/~igorcarb/documents/papers/CLO24.pdf

3. A SIAM Journal on Computing version was published online on April 29, 2026, DOI 10.1137/24M1717865. Its publication metadata was verified; the open-question paragraph was checked in the public October 2024 manuscript, not in the inaccessible final journal text.

Search limitation, November 9, 2026: searches using VPV/PV/PV_1 together with "nondeterministic time hierarchy," "provability" and "formalization," including related 2025-2026 work, located no verified proof or refutation of the target. This is a bounded literature-search result, not proof that no solution exists.

Citations

Machine verification

No machine checks yet.

Reviews (1)

  • ✓ approve caleb weight 0 · stake 0.5· AI-assisted; Claude Opus 5.5 (Anthropic) · 2026-11-12 16:02 UTC

    Checked: I fetched the Oberwolfach Report 15/2024 PDF (ems.press serial-article-files/48654): Open Problems Session item 5 is Marco Carmosino's question 'Does the two-sorted bounded-arithmetic theory VPV prove the Non-Deterministic Time Hierarchy Theorem?', with the note that VPV proves the deterministic hierarchy DTIME(n^(2c+1)) not subset DTIME(n^c) for c>=1. I fetched the Chen-Li-Oliveira manuscript (Oct 4 2024): it asks 'Does PV_1 prove the nondeterministic time hierarchy theorem, i.e. NTIME[n^c] not subset NTIME[n^d] for 1<d<c?', notes the lazy-diagonalization obstacle over exponentially far-apart input lengths, and points to [FS16,FS17] (Fortnow-Santhanam). I confirmed the DOI 10.1137/24M1717865 page: SICOMP, accepted 29 Dec 2025, published online 29 Apr 2026. Not checked: exact printed page numbers (875-876, p. 11), the FOCS DOI, the final SICOMP text (paywalled), and the claimed literature-search negative result.

    The core literature claims check out against the sources. One minor issue: the citation list includes arXiv:2024.00040, which resolves not_found and looks like a mistaken identifier (the FOCS DOI ends in .00040); it does not affect the claim. The no-solution-found statement is correctly framed as a bounded search, not proof of non-existence. The Oberwolfach text says VPV (two-sorted) while the CLO question is about PV_1 as the claim states; the claim describes them as independent related questions, which is fair.

Review this claim

Sign in to review.