将合并解决技术扩展到一类QBF证明系统中

《ACM Transactions on Computation Theory》:Extending Merge Resolution to a Family of QBF-Proof Systems

【字体: 大 中 小 】 时间:2026年01月03日 来源:ACM Transactions on Computation Theory

编辑推荐:

  Merge Resolution (MRes) 证明系统的扩展研究,提出 MRes-R 系统通过任意预定的完全表示 R 存储反模型信息,采用一致性检查规则替代等价性检查,证明系统可保持多项式时间可验证性。研究显示 MRes-R 的定常版本比原系统强得多,并利用完成原理公式 CRn 提升下界证明,证明使用不同完全表示的证明系统保持 CRn 的困难性。

  

摘要

合并解决(MRes [6])是一种最近引入的用于处理错误QBF(Quantified Boolean Formula)的证明系统。与其他已知的QBF证明系统不同,它在证明过程中为通用玩家(即反模型)构建了获胜策略,这些策略以合并映射的形式呈现。合并映射是确定性分支程序,在这些程序中同构检查非常高效,因此MRes是一个多项式时间可验证的证明系统。
在本文中,我们介绍了一类证明系统MRes-R,其中反模型的信息存储在任何预定义的完整表示中。R因此,对于每种可能的完整表示,我们都有一个在MRes-R中既可靠又具有反驳完备性的QBF证明系统。为了处理这些任意表示,我们在MRes-R中引入了一致性检查规则,而不是使用MRes中的同构检查规则。因此,这些证明系统不是多项式时间可验证的(即非P类)。结果表明,使用合并映射过于严格;通过略微修改规则,可以用任意表示来替代合并映射,从而得到多种有趣的证明系统。
我们将这些新系统与[11]中提出的隐式证明系统进行了关联,该系统旨在使用类似于MRes的子句策略对来解决DQBF(Dependency QBF)问题。我们采用了[11]中推荐的OBDD(有序二进制决策图)表示方法,并推断出MRes-R中的证明系统的“有序”版本在一些额外限制条件下也是多项式时间可验证的。
为了展示这些系统的强大性能,我们证明了MRes-R中的规则版本比普通的MRes强大得多。我们还提高了普通MRes的下界([7]中的结果),证明了[25]中提出的完成原理公式(CRn),这些公式对普通MRes来说是难以处理的,也对任何MRes-R中的证明系统都是难以处理的。因此,本文将普通MRes的下界提升到了一个包括各种完整表示(不仅仅是合并映射)的证明系统类别。这证明了即使将MRes中的弱同构检查改为更强的一致性检查,CRn公式的难度仍然保持不变。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号