• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >Uniform Proof Complexity
【24h】

Uniform Proof Complexity

机译：统一的证明复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We define the notion of the uniform reduct of a propositional proof system as the set of those bounded formulas in the language of Peano Arithmetic which have polynomial size proofs under the Paris-Wilkie-translation. With respect to the arithmetic complexity of uniform reducts, we show that uniform reducts are Π_1~0-hard and obviously in ∑_2~0. We also show under certain regularity conditions that each uniform reduct is closed under bounded generalisation; that in the case the language includes a symbol for exponentiation, a uniform reduct is closed under modus ponens if and only if it already contains all true bounded formulas; and that each uniform reduct contains all true Π_1~b (α)-formulas.
机译：我们将命题证明系统的统一约简的概念定义为Peano算术语言中具有巴黎-威尔基翻译的多项式大小证明的那些有界公式的集合。关于均匀约简的算术复杂度，我们表明均匀约简是_1_1〜0-hard，显然在∑_2〜0中。我们还证明，在一定的规律性条件下，每个统一归约都在有界概括下是封闭的。在该语言包括求幂符号的情况下，当且仅当它已经包含所有真实的有界公式时，才会在惯用ponens下关闭统一归约；并且每个均匀约简都包含所有真实的Π_1〜b（α）公式。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号