paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Build your own clarithmetic II: Soundness

构建你自己的 clarithmetic II:可靠性
LMCS vol.Volume 12, Issue 32017匹配度 1/10 · 该论文属于可计算性逻辑与算术证明论,研究 clarithmetic 系统的可靠性及证明中提取复杂度受限算法,与用户核心方向(LLM/Agent 与静态分析、浮点程序分析、贝叶斯程序分析的交叉)无直接关联;虽涉及定理证明与形式化,但不涉及静态分析或 LLM/Agent。引用 7 inbox
Giorgi Japaridze
crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:为参数化 clarithmetic 系统 CLA11(P1,P2,P3,P4) 证明可靠性,并说明其定理对应可提取的复杂度受限算法解。

本文是 clarithmetic 系列第二部分,专注可靠性证明。Clarithmetic 是基于可计算逻辑的数论,公式表示交互式计算问题,“真”即存在算法解;解的时间、空间与振幅复杂度约束产生不同版本。作者提出参数化系统 CLA11(P1,P2,P3,P4),机械调节 P1、P2、P3 可设定振幅、空间与时间复杂度,自动得到相对于目标 tri-complexity 类可靠且完备的理论:每个定理表示该类中的交互数论问题,且解可从证明自动提取;调节 P4 可在牺牲递归可公理化但保持简洁的前提下,将外延完备性强化为内涵完备性。第一部分已引入系统并证明完备性,本文证明可靠性。

问题
如何为基于可计算逻辑、按时间/空间/振幅复杂度参数化的 clarithmetic 理论建立可靠性,使定理对应可在目标复杂度类中求解的交互数论问题。
方法
引入参数化系统 CLA11(P1,P2,P3,P4),通过调节 P1、P2、P3 分别控制振幅、空间与时间复杂度;本文作为第二部分给出其可靠性证明,并讨论 P4 对外延/内涵完备性的影响。
评估
以形式化证明给出可靠性定理,与第一部分已证的完备性相配合;不涉及实验评估。
原文摘要(Abstract)

Clarithmetics are number theories based on computability logic (see http://www.csc.villanova.edu/~japaridz/CL/ ). Formulas of these theories represent interactive computational problems, and their "truth" is understood as existence of an algorithmic solution. Various complexity constraints on such solutions induce various versions of clarithmetic. The present paper introduces a parameterized/schematic version CLA11(P1,P2,P3,P4). By tuning the three parameters P1,P2,P3 in an essentially mechanical manner, one automatically obtains sound and complete theories with respect to a wide range of target tricomplexity classes, i.e. combinations of time (set by P3), space (set by P2) and so called amplitude (set by P1) complexities. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a solution from the given tricomplexity class and, furthermore, such a solution can be automatically extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a solution from the given tricomplexity class is represented by some theorem of the system. Furthermore, through tuning the 4th parameter P4, at the cost of sacrificing recursive axiomatizability but not simplicity or elegance, the above extensional completeness can be strengthened to intensional completeness, according to which every formula representing a problem with a solution from the given tricomplexity class is a theorem of the system. This article is published in two parts. The previous Part I has introduced the system and proved its completeness, while the present Part II is devoted to proving soundness.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) ·

BibTeX
@article{paperbot169,
  title = {Build your own clarithmetic II: Soundness},
  author = {Giorgi Japaridze},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 12, Issue 3},
  year = {2017},
  doi = {10.2168/lmcs-12(3:12)2016}
}