揭示精确认证中轨道间隙导致的计算困难,为复杂性分析提供新框架。
Descent Before Hardness: Orbit-Gap Obstructions in Exact Certification
- 基于正确性商的闭包轨道构造,识别不可下降的目标
- 发现原始语法、动作计数等在轨道间隙下无法通过验证
- 适用于形式化验证与模型检查中的复杂性分析场景
可解性测试通常基于输入语法:支持图树宽、局部系数模式、后门测试或动作计数边界。在这些测试可用于下界证明或算法实现前,必须在精确认证问题本身上定义谓词。等价表示应获得相同判断结果。语义对象是正确性商,其类为具有相同正确输出的状态。保持正确性的表示变换生成闭包轨道。若目标在某闭包轨道内变化,则存在轨道间隙,导致无法下降。当正负轨道包络不相交时,可实现完全闭包不变分类;此时正轨道包络即为最小精确分类器,且可通过轨道代表元实现算法化。研究区分了三个层次:下降层揭示原始局部语法、原始动作与坐标计数、原始支持图谓词的轨道间隙障碍;后下降复杂性层对下降后对象应用常规归约:图谓词下界可通过动作间隙图提取传递,当宽度约束为输入时,Action-Gap-Treewidth 为 NP 完全;认证层则询问代理是否可下降:对于分裂代理 $b\wedgeφ(z)$,SAT 归约为非下降,UNSAT 归约为下降。正向情形使用商保持的标准化或目录化再进行模型检查;有界商大小、构造商的有界完整 Gaifman 树宽、稀疏一元间隙证书及严格边际扰动球,均在商构造后给出显式代价界。
原文摘要 · Abstract (English)
Tractability tests are often computed from input syntax: support-graph treewidth, local coefficient patterns, backdoor tests, or action-count bounds. Before such a test can be lower-bounded or made algorithmic, it must define a predicate on the exact-certification problem itself. Equivalent presentations must receive the same verdict. The semantic object is the correctness quotient, whose classes are states with the same correct outputs. Correctness-preserving presentation moves generate closure orbits. A target that changes inside one closure orbit has an orbit gap and fails descent. Exact closure-invariant classification is possible exactly when the positive and negative orbit hulls are disjoint; the positive hull is then the least exact classifier, and computable orbit representatives make the classifier algorithmic. The results separate three layers. The descent layer gives orbit-gap obstructions for raw local syntax, raw action and coordinate counts, and raw support-graph predicates. The post-descent complexity layer applies ordinary reductions to descended objects: graph-predicate lower bounds transfer through action-gap graph extraction, and Action-Gap-Treewidth is NP-complete when the width bound is part of the input. The certification layer asks whether a proxy descends: for split proxies $b\wedgeφ(z)$, SAT reduces to non-descent and UNSAT reduces to descent. Positive regimes use quotient-preserving normalizations or catalogues before model checking; bounded quotient size, bounded full Gaifman treewidth of the constructed quotient, sparse unary-gap certificates, and strict-margin perturbation balls give explicit cost bounds after quotient construction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。