不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

Cook的文章“定理证明过程的复杂性”(部分译文)

已有 2910 次阅读 2020-8-3 14:40 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| Cook的文章

P vs NP问题的提出缘起于定理证明过程的复杂性(The Complexity of Theorem-Proving Procedures1971年)。分享此文的部分译文。


定理证明过程的复杂性

摘要

文章指出,不确定性图灵机在多项式时间内解决的任何识别问题都可以归约为判定给定命题公式是否为重言式的问题。粗略说,这里归约意味着,如果第二个问题可用oracle解决,那么第一个问题就可以在多项式时间内确定性地解决。根据此归约的概念,定义了多项式复杂性,并且指出判定重言式的问题与判定两个给定图中的第一个图是否与第二个子图同构的问题具有相同的多项式复杂性。文章还讨论了其他例子,介绍和讨论了一种量度谓词演算证明过程复杂性的方法。

原文:https://www.inf.unibz.it/~calvanese/teaching/11-12-tc/material/cook-1971-NP-completeness-of-SAT.pdf

Cook定理译文.pdf




https://m.sciencenet.cn/blog-2322490-1244831.html

上一篇:南法西班牙现代绘画寻踪(1)
下一篇:师徒对话 - “问题”与NP、AI (2014/5)

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 22:13

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部