...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>ACM transactions on computational logic >The NP Search Problems of Frege and Extended Frege Proofs
【24h】

The NP Search Problems of Frege and Extended Frege Proofs

机译：弗雷格和扩展弗雷格证明的NP搜索问题

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study consistency search problems for Frege and extended Frege proofs-namely the NP search problems of finding syntactic errors in Frege and extended Frege proofs of contradictions. The input is a polynomial time function, or an oracle, describing a proof of a contradiction; the output is the location of a syntactic error in the proof. The consistency search problems for Frege and extended Frege systems are shown to be many-one complete for the provably total NP search problems of the second-order bounded arithmetic theories U-2(1) and V-2(1), respectively.
机译：我们研究了Frege和扩展Frege证明的一致性搜索问题，即在Frege和扩展Frege证明的矛盾中发现句法错误的NP搜索问题。输入是描述矛盾证明的多项式时间函数或oracle。输出是证明中语法错误的位置。对于二阶有界算术理论U-2（1）和V-2（1）的可证明的总NP搜索问题，分别显示了Frege和扩展Frege系统的一致性搜索问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号