RKU v1.1: Proof Complexity Interface——Resource-Bounded Proof Complexity and Probabilistically Checkable Proofs Unification
This paper extends RKU v1.0 framework, providing rigorous interface with Proof Complexity/PCP. Unifies RKU resolution resources $\mathbf{R}=(m,N,L,\varepsilon)$ with proof complexity: proof budget $L$ equivalent to proof size lower bounds, statistical indistinguishability bridges with probabilistic verification. Core contributions include: (1) RKU-Proof Complexity equivalence theorem, proving resource bounds entail proof length lower bounds; (2) PCP extension, unifying statistical $\approx$ with probabilistic checkability; (3) Phase diagram and resource curves; (4) Numerical verification and core code, with $n=10/100/1000$ yielding lower bounds $100/10000/1000000$. RKU-PC interface does not change original incompleteness, but resource-izes proof systems: Established result: Cook-Reckhow theorem asserts that if there exists polynomial-size proof system proving all positive sentences, then $\text{NP}=\text{coNP}$; PCP theorem shows NP has probabilistically checkable proofs. Results unify logical undecidability with statistical indistinguishability, providing recognizability proofs and phase diagrams. \textbf{Note}: Numerical values based on Frege system simulation and high-precision calculation; low $n$ sampling average deviation $<1\%$, approaching lower bounds as $n$ increases.
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2025-10-15
- DOI
- https://doi.org/10.5281/zenodo.17362211
- Primary Topic
- Formal Methods in Verification
- Type
- article
- Field-Weighted Citation Impact
- 0.00