最近我与一个工作在NP问题实际求解前沿的同事对话： 同事：我认为，如果取消了“不确定性图灵机（NonDeterministic Turing Machine NDTM）”这个概念，把NP定义成“确定性图灵机（Deterministic Turing Machine DTM）”在多项式时间内可验证的问题类，不会影响NP问题的实际求解，对NP完备理论也不会产生影响。 柳渝：此议题涉及到二个层次，NP问题的实际求解和NP问题的理论研究。若取消NDTM，就NP理论而言，人们自然会问诸如此类问题： －为什么所有关于NP 完备 理论的文献和书籍，都要花重要的篇幅讲NDTM？ －若NDTM无用，为什么仍然要将此无用的概念灌输给学子们，混淆他们的认知，让他们越学越晕？ －NP 完备 理论的核心是Cook定理（注），而Cook定理的陈述和证明都是建立在NDTM基础之上的，如果取消了NDTM，如何阐述Cook定理？如何理解NP完备理论？ 注：The original statement of Cook’s theorem was presented in Cook’s paper entitled “The complexity of theorem proving procedures” as: － Theorem 1 If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}. The main idea of the proof of Theorem 1 was described: －Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form (CNF) such that A(w) is satisfiable iff M accepts w. Thus ¬A(w) is easily put in disjunctive normal form (using De Morgans laws), and ¬A(w) is a tautology if and only if w ̸∈ S. Since the whole construction can be carried out in time bounded by a polynomial in | w | (the length of w), the theorem will be proved.
It is in the admission of ignorance and the admission of uncertainty that there is a hope for the continuous motion of human beings in some direction that doesn't get confined, permanently blocked, as it has so many times before in various periods in the history of man. - Richard P. Feynman (1918 – 1988) whatIsCookTheorem.pdf 论文已在 arXiv 发布： http://arxiv.org/abs/1501.01910。
“P versus NP”是计算机领域中一个平凡又不凡的问题。说“平凡”，是因为此问题缘起于探讨有效求解大量的应用问题，诸如：旅行商问题，图染色问题，作业调度问题等等；说“不凡”，是因为此问题是计算机理论的核心问题，又是Clay Mathematics Institute收录的七个千禧年难题之一，虽然学术界已投入了巨大资金和人力，至今却没有实质性的进展。 Bill Gasarch于2002年和2012年（http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf），对100和152计算机理论前沿的研究者，进行了关于“P versus NP”前途的调查，是对该问题现状的很好解读。Hemaspaandra在介绍2012的调查时，悲观地说： －我希望在遥远的未来，人们读到这四篇文章，可以帮助他们了解，在P versus NP还没得到解决的黑暗年代里人们的思想状态。 （ I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved. ） 我们的“NP理论”工作就是针对此问题的探索，我们认为此问题实际上隐含着一直未被人们重视的认知偏差，以致于成了名副其实的「皇帝的新衣」，我们希望借此工作能引起人们对认知基本问题的重视，以及对中西文化互补性的实践和思考，。。。 文章“什么是NP？－ 解读中国哲学悖论“白马非马（What is NP? - Interpretation of a Chinese paradox white horse is not horse）”，就是我们工作的第一阶段的一个总结，希望与感兴趣的同事切磋交流。此外，这里出现的一些观点、术语等，会与流行的有所不同，以后逐步介绍。
两篇来自 Bruce Friedman的博文 http://labsoftnews.typepad.com/lab_soft_news/2012/08/data-vs-information-the-emr-readability-problem.htmlhttp://labsoftnews.typepad.com/lab_soft_news/2012/08/data-vs-information-the-emr-readability-problem-part-ii.html 其中审视了当前医疗信息结构化所忽略的一些问题，主要是在强调结构化的同时，忽略了对数据的加工、忽略数据的人可读性所能带来的好处。机器和人不一样，各自有各自的特点和需求，如何在二者之间取得一个很好的权衡点，是件不容易的事情，CDA从诞生至今，至少朝着这个方向一直在努力，而且FHIR中也强调了这一特性，值得让人去关注。
ACM通讯上的一篇综述： The Status of the P Versus NP Problem 作者简介: Lance Fortnow Biography Lance Fortnow is a professor of Electrical Engineering and Computer Science at Northwestern University specializing in computational complexity and its applications to economic theory. He also hold a courtesy appointment at the Managerial Economics and Decision Sciences department in the Kellogg Graduate School of Management and an adjoint professorship at the Toyota Technological Institute at Chicago. Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Northwestern in 2008, Fortnow was a professor at the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam. Fortnow's research spans computational complexity and its applications, most recently to micro-economic theory. His work on interactive proof systems and time-space lower bounds for satsifability have led to his election as a 2007 ACM Fellow. In addition he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97. Among his many activities, Fortnow served as the founding editor-in-chief of the ACM Transaction on Computation Theory , serves as chair of ACM SIGACT and sits on the council of the Computing Community Consortium . He served as chair of the IEEE Conference on Computational Complexity from 2000-2006. Fortnow originated and co-authors the Computational Complexity weblog since 2002, the first major theoretical computer science blog. He has over 1200 followers on Twitter . Fortnow's survey The Status of the P versus NP Problem is CACM's most downloaded article. Fortnow is currently working on a book expanding on that article.
汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语！ Chinese is one of the six equally effective official languages of the United Nations. Not to discriminate against Chinese, please! P对NP：请郝克刚教授等专家指教（一） （ 一般背景知识汇报 ， 无穷化版本下的“P 对 NP” ） 求教心切，由于种种原因，下文里面错误难免。 请您不吝批评与指教！衷心感谢！ 主要相关数学分 支：公理集合论，图论， 概率论 ；以及理论计算机科学。 一、术语的缩写、相关数学知识简介 NDTM （ NTM ）， non-deterministic Turing machine ，非确定型图灵机； DTM （ TM ）， deterministic Turing machine ，确定型图灵机； NPC ， NP-complete ， NP- 完全； NPI ， NP-Intermediate ， NP里 不属于 P 类且不属于 NP- 完全问题，早期指“人们 不知道是属于 P 类还是属于 NP- 完全类，还有待于证明其归属”； CH ， continuum hypothesis ， 连续统假设 ； TSP ， traveling salesman problem ， 旅行推销员问题 ； SAT ， Boolean satisfiability problem, Boolean 逻辑可满足性，是由 Cook 证明的第一个 NPC 问题 。 ZF ， Zermelo–Fraenkel set theory ， 策梅洛 - 弗伦克尔公理系统； ZFC ， Zermelo–Fraenkel set theory with the axiom of choice ，承认选择公理的 策梅洛 - 弗伦克尔公理系统 ； NBG 或 GB ， NBG of Neumann–Gdel–Bernays ， 冯 · 诺伊曼、 P. 贝尔奈斯、 K. 哥德尔 集合论公理系统 。 a ，可数无穷基数； c ，连续统的基数（全体实数集的基数）； f ，全体几何曲线集合的 基数 。 CH 的基本含义： The hypothesis, due to G. Cantor (1878), stating that every infinite subset of the continuum R is either equivalent to the set of natural numbers or to R itself. 目前已知“ 连续统假设在 ZF （或 GB ）中是不可判定的，它即不能被证明，也不能被否证。 ” 换言之，在著名的集合论公理系统中，都不足以解决连续统假设。这正是人们不断地寻求新公理系统的主要原因。人们总希望能找到科学的为大家所能接受的公理系统，并且得以解决著名的未解决的问题。 “ Formal unsolvability is understood in the sense that there does not exist a formal derivation in the Zermelo–Fraenkel system ZF either for the continuum hypothesis or for its negation. ” 阿列夫 Aleph 是个有争议的问题。据说有人认为 阿列夫 2 与连续统的基数相等，还有人认为 阿列夫 可数无穷 仍然小于连续统的基数。所以，我不采用 阿列夫 来研究“ P 对 NP ”，而是采用数学意义更为直观明确的 Cantor 无穷级数第二序列（ a , c , f , h , i , 等等）来表述。在 1997 年《百科知识》、 1999 年《哲学研究》等文章里开始使用。 二、本人相关背景简介 我是一名普通的基础课教师，天生的笨傻。每年能用于真正“科研”的时间，十分有限。为了完成岗位职责，要花去大量的时间。 上帝啊！ 我太累了 ！ 我没有时间 ！ 因此推出“ P 对 NP ”完全证明的个人观点，肯定是十分艰难和缓慢的。 本文博文作为正式的介绍材料之一 。 期待有关专家指导俺修改之！ 1993 年暑假，某天夜里后半夜，想到在“ 有穷情况” 下的 P 和 NP 关系。 这个发现，是以生命为代价换来的！ 大约到 1995 年初，真傻又做出“ 无穷版本” 下的 P 和 NP 关系：是一个著名数学问题的特定解释。 2011 年 3 月，给出概率意义下的有穷直接证明。 本人专业背景简介 我目前是天津大学（ 985 大学）在岗的“ 模式识别与智能系统”和“软件工程” 2 个专业的硕士生导师，工学博 士学位。曾经开设硕士生选修课《人工智能专题》多年，以史忠植先生的《高级人工智能》为主要参考书。 从2002年开始 主讲硕士生选修课《模糊理论及应用》至今。 我 1988 年硕士入学后不久，就听说了“ P 对 NP ”问题。该问题的核心，数次被两位教授重复。一位教授开设硕士生《数据结构与算法》多年，俺跟该教授上过这门课；该教授在 1980 年代，就指导过东欧来天津大学的访问学者。另一位教授在图论方面有较深的造诣，曾经对两个经典问题做出世界最好结果。由于未征求这两位教授的意见，此处只能隐去他们的姓名，以避免可能对他们产生的某种不必的负面影响。 其中的图论教授，数次向我们讲解“ P 对 NP ”的核心，并推荐了名著《 GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness . New York: W. H. Freeman, 1979. 》。我从系资料室（现更名为学院资料室）借阅该书的汉译本 20 余年。由本学院上届领导批准，几年前将该书赠送给我。 感谢这位好心的领导！礼轻情意重！ 因此，“ P 对 NP ”是属于我专业背景的科学问题（数学 - 计算机科学）。 三、 对“ P 对 NP ”核心的个人理解 3.1 “ P 对 NP ”定义的核心 P 是 DTM （确定型图灵机）在多项式时间内的可判定问题类。 这里的“问题类”，常被记为“语言类”。“可判定”是可计算性、计算复杂性里面使用的术语。可判定的一个通俗理解，就是可以求解，可以得到正确的答案。典型的 P 问题，有常见的排序 sorting ，数值矩阵的乘法。 NP 是 DTM （确定型图灵机）在多项式时间内的可验证问题类。 NP 是 NDTM （ NTM ，非确定型图灵机）在多项式时间内的可判定问题类。 DTM 与 NDTM 关系的一个直观解释： 非确定型图灵机是一种能够同时进行多路计算的“并行”的图灵机，并且限制这些并行的图灵机之间不能相互通讯。 A nondeterministic Turing machine is a "parallel" Turing machine that can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannot communicate. 3.2 “ P 对 NP ”的有关主流看法 显然， P 包含在 NP 里面。是否所有的 P 都是 NP ，是“ P 对 NP ”的表述方式之一。 NP 里面最难的称为 NPC （ NP 完备的）。 NP 里面的任何问题，都可以在多项式时间内归约为 NPC 。 如果 NPC 找到了多项式时间求解算法，则证明 P=NP 。 如果证明 NPC 必须使用指数时间，则证明 P ¹ NP （ P 不等于 NP，也有人记为 P ！ =NP ）。 如果 P ¹ NP ，则可能存在“不是 P ，又不是 NPC ”的中间类型 NPI 。找到一个 NPI ，则等效于证明 P ¹ NP 。 NPC 的例子很多。第一个 NPC 是 SAT ，常见的自然问题有 TSP 等。 到目前为止，“ P 对 NP ”未见主流承认的答案。 Clearly, is contained in . However , it is not known whether or not the containment is proper . The problem of whether or not equals ( ?) can justly be called the most celebrated open problem in the theory of computation. The significance of this question is due to the fact that many practically important problems are known to be in , whereas it is not known whether or not they are in . In fact, all known deterministic algorithms for these problems are exponential as far as time is concerned. Thus, a proof of would make all of these problems tractable. Most exponential time algorithms are marely variations on exhaustive search, whereas polynomial time algorithms generally are possible only through the gain of some deeper insight into the structure of a problem. 大多数指数时间算法只是穷举搜索的变种，而多项式时间算法通常只有在对问题的结构有了某些比较深入的理解之后才有可能给出。 现有的研究与证明方法主要有三大类：对角化 diagonalization 、电路复杂性 circuit complexity 、证明复杂性 proof complexity 。但国际学术界普遍的看法是这些方法都不能得到彻底的结果。一般认为，“不同数学领域的意外结合”、“ P 或 NP 新特征的使用”、“新的电路复杂性下界证明方法”以及“对角化的新变形”等是可能获得新结果的途径。 3.3 对“ P 对 NP ”的一些个人看法 由于“重复发表”、“首次发表”等现行科技规范问题，这里只能就我的某些看法想有关老师汇报。其余的看法，希望能在“有同行评审的期刊”发表。敬请您的指教！ （ 1 ）“ P 对 NP ”的难度（为什么该问题如此难？） ① 由 NP 定义可知“对于 NDTM ， P=NP ”，因此 “对于 DTM ， P ¹ NP ”才是研究的重点 。这十分类似希尔伯特第四问题，“ P 对 NP ”问题描述的不确定性，误导了人们的研究。造成了 “ P 对 NP ”研究额外的困难性。 缺少对 DTM 和 NDTM 结构差异的充分使用，是导致“ 对于 DTM ， P ¹ NP ”长期缺乏明确结论的原因之一。 ② 目前的以及历史上出现的各种主流研究方法，都集中在 P 或 NP 问题类的数量性质研究上。 从问题类角度看，由于 NPC 类、 P 类只是在 DTM 上计算“速度”的差异，只是一种“量”的区分，而不像“可计算性”是一种质的区分，这是引起 “ P 对 NP ”困难性的 原因之二。因为证明所采用的“逻辑”，通常是成立、不成立两种明确状态（质）划分的。 ③ 如果能证明对于 DTM ， P 不等于 NP ，则无穷版本下的 NPI 就是 Cantor 原本意义下连续统假设的关系。预计可以得出不接受连续统假设的结论。 （ 2 ）“ P 对 NP ”完全证明的结论 “ P 对 NP ”实际上是三个更具体问题的合成： ① 在 NDTM 中 P 等于 NP ； For a NDTM, P=NP; ② 在 DTM 中 P 不等于 NP ； For a DTM, P ¹ NP; ③ 没有关于所采用的理论计算机模型的必要说明，则具有独立性。 从形式语言的表示看， 郝克刚 老师《纠正对 NP 问题的错误理解（ 3 ） -- 对一位网友文章的评论》（ http://blog.sciencenet.cn/home.php?mod=spaceuid=506146do=blogid=530828 ） 表述是很准确的。 这里仍然采用“ 没有 …… 必要说明 ”，基本意图是想提供多的信息：命题对公理系统的独立性，除了该命题对证明所采用的公理系统“独立”外（直观“独立”的意思），公理系统的信息量不够，也可能造成独立。例如实系数一元二次方程，当根的判别式小于 0 时，在实数域是没有解的。这是由公理系统信息量不够引起独立的直观类比或解释。 参见 1974 年的 Chaitin 定理。一般认为， Chaitin 的三条定理，是对 Kurt Friedrich Gdel 的 哥德尔 第一不完全定理（ Gdel's first incompleteness theorem ）的信息论意义下的具体化 。（ Gdel incompleteness theorem 在《苏联数学百科全书 Encyclopedia of Mathematics》扩展版， http://www.encyclopediaofmath.org/index.php/G%C3%B6del_incompleteness_theorem 。 Kurt Gdel 在《Stanford Encyclopedia of Philosophy》， http://plato.stanford.edu/entries/goedel/ ） （ 3 ）“ P 对 NP ”完全证明结论的三类证明 ① 有穷形式下形转化的直接证明； ② 无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的“连续统假设”； ③ 概率形式、有穷形式下的直接证明。 其中“ ③ 概率形式、有穷形式下的直接证明”，还未公开过。计划争取英文文章。 在 2011 年初夏，以文字形式，向党组织汇报过（党员创优活动的汇报，一个笔记本。 恳请党组织保留该笔记本一些时间 ，感谢党的指导与关怀！） 。 上面的“ ① 有穷形式下形转化的直接证明； ② 无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的‘连续统假设’”， 1995 年以《 从 NP 结构到超级计算机分类理论》为题目，在天津大学百年校庆研究生院研究生学术报告会（1 995 年 10 月初）公开讲解过。可惜没有录音或录像，希望有人愿意证明我讲过。 “ ① 有穷形式下形转化的直接证明”的细节，计划争取英文文章。 因此，本博文主要汇报“ ② 无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的‘连续统假设’”。 （ 4 ）无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的“连续统假设” 该证明发表在 2011 年 TTU 的《 A non-canonical example to support that P is not equal to NP 》，其核心在 2008 年《 密码学与非确定型图灵机 》里扼要介绍过。 “无穷形式 / 版本”的基本意思，是将 DTM 、 NDTM 的运行时间取为无穷大（可数无穷步。接受“实无穷”，令字母表、状态数为可数无穷即可，这很自然；坚定的“潜无穷”论者可能提出怀疑。）。 DTM 此时只有一个新状态、一共生成 a 个状态；而 NDTM 此时产生 | Q-F | a 新状态，以及指数界数目的总状态。 直观地说：限制 NDTM 的转移函数每次只产生一个转移状态，则该最小的 NDTM 就退化为一个 DTM 。所以，容易证明， DTM 至多用指数时间就可以模拟一个对应的 NDTM 。这等价于“ P 包含在 NP 里面”。 如果证明“ DTM 必须用指数时间就才能模拟一个对应的 NDTM ”，则从某种意义上讲，就等价地证明的“ P 不等于 NP ”。而这并不容易，所以 2011 年 TTU 的文章采用“支持 P 不等于 NP ”的说法（ A non-canonical example to support that P is not equal to NP ）。 演绎证明的实质，是将“公理”包含的信息，以某种方式显示出来，所以“演绎证明的结论是前提蕴含的”。假如不是前提蕴含的，就是“独立的”。 假如找到 NPI ，则在其无穷化版本下，等价于否证 Cantor 原本意义下的连续统假设。 目前众所周知的康托三分集（ Cantor ternary set ），显然与连续统假设（ continuum hypothesis ）的研究有直接的关系。 （ 5 ）关于“ P 对 NP ”的独立性 ① 如果没有明确是用 DTM 或 NDTM 求解，则 “ P 对 NP ” 具有独立性。 这是说 “ P 对 NP ”对“用 DTM 或 NDTM 求解 ”独立，而不是对现有的公理集合论系统（ ZF、NGB 等 ）独立 。 这类似：实系数一元二次方程，当根的判别式小于 0 时，在实数域无解；在复数域有解。 又如， 1975 年 Baker 、 Gill 和 Solovay 报道的“存在不同的计算模型 A 、 B ，使得 P A =NP A 、 P B ¹ NP B 分别成立。” ② 承认“对 DTM ， P 不等于 NP ”，则 无穷版本下的 NPI ，就是的 Cantor 原本意义下的连续统假设 CH 。 无穷版本下 NPI 的存在性，对 目前现有的公理集合论系统（ ZF、NBG 等 ）独立。 所以 1975 年 Ladner 证明“如果 P ¹ NP ，则 NPI=(NP - P) 不是空集”以及 1993 年 Zimand 证明如果 NP - P 不空则很大（ If not empty, NP - P is topologically large ），都不能给出确定的结果。 假如 P 不等于 NP ，则 NPI 对应一种介于多项式和指数之间的时间增长方式。由于 Cantor 没有构造出这样的增长方式，所以才在 1878 年提出连续统假设：连续统子集的基数，要么是自然数，要么还是连续统的基数。康托三分集的基数还是连续统的基数 c ；可以从连续线段中抽取有穷或无穷个离散点（自然数集的基数，有穷基数，或可数无穷基数 a ）。 四、请教 4.1 关于 真傻 的叙述 （ 1 ）以上关于无穷化版本下的“ P 对 NP ”问题的看法是否介绍清楚？ （ 2 ）关于“ P 对 NP ”问题难度的解释，《 A non-ca nonical example to support that P is not equal to N P 》的介绍是否清楚？ 4.2 创新性小结与说明 我的方法基本没有创新：属于“不同数学领域的意外结合”和“P或NP新特征的使用”，并没有超出主流的预期。 主要创新： （1）提出“完全证明Full proof”作为数学证明的新标准； （2）建立无穷版本下的NPI与Cantor原本意义下连续统假设的关系。 其它的都是主流预期的，没什么让人耳目一新的。惭愧！ 4.3 有关的问题请教 （ 1 ） “ 2TSP 是 P ， 3TSP 是 NPC ”的证明，还有在 SCI、EI 期刊发表的可能性吗？ （ 2 ） “ P 对 NP ”相关问题对 ZF 的独立性，是否有进一步研究的必要和可能？ 真诚期待有关专家的批评与指教。 衷心感谢！ 主要参考文献： COOK S. The P versus NP Problem, official problem description , . http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf ALLENDER E. A status report on the P Versus NP question . Advances in Computers , 2009, 77: 117-147. FORTNOW L. The Status of the P versus NP Problem . Communications of the ACM , 2009, 52(9): 78-86. SIPSER M. The history and status of the P versus NP question . Proceedings of the 24th Annual ACM Symposium on the theory of Computing’ 92 (Canada) , 1992, pp 603–618. COOK S. The importance of the P versus NP question . Journal of the ACM , 2003, (50)1: 27-29. HAZEWINKEL M. Encyclopaedia of mathematics: an updated and annotated translation of the Soviet “Mathematical encyclopaedia” . Dordrecht: Kluwer Academic Publishers, 2001. HOPCROFT J E, MOTWANI R M, ULLMAN J D. Introduction to automata theory, languages, and computation (Third edition) . New Jersey: Ad dison Wesley , 2006. GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness . New York : W. H. Freeman, 1979. Nondeterministic Turing Machine . http://mathworld.wolfram.com/NondeterministicTuringMachine.html CHAITIN G J. Information-theoretic computational complexity . IEEE Transactions on Information Theory , 1974, 20(1): 10-15. 中国大百科全书•数学 . 北京 : 中国大百科全书出版社 , 1988. BAKER T, GILL J, SOLOVAY R. Relativizations of the P =? NP question . SIAM Journal on Computing , 1975, 4(4): 431-442. LADNER R E. On the structure of polynomial time reducibility . Journal of the ACM , 1975, 22(1): 155-171. ZIMAND M. If not empty, NP - P is topologically large . Theoretical Computer Science, 1993, 119: 293-310. Weisstein, Eric W. "Nondeterministic Turing Machine." From MathWorld--A Wolfram Web Resource . http://mathworld.wolfram.com/NondeterministicTuringMachine.html 杨正瓴 . 从 NP 结构到超级计算机分类理论 . 天津大学百年校庆研究生院研究生学术报告会（一等奖论文），和天津大学百年校庆自动化系学术报告会， 1995 年 10 月 . 杨正瓴 . 人脑有多复杂？ . 百科知识， 1997 ， 7 （总第 216 期）： pp39 – 40. 杨正瓴 . 人脑复杂性的估计及其哲学意义 ，《中国新时期社会科学成果荟萃》， 1999 ，第 1 卷 p296 。卢继传 主编，中国经济出版社，北京， ISBN 7 – 5017 – 4100 – X/G. 374 ， （第 2 编，哲学，第 4 章，自然辩证法） . 杨正瓴，林孔元 . 人类智能模拟的“第 2 类数学（智能数学）”方法的哲学研究 . 哲学研究， 1999, (4): 44-50. 杨正瓴 . 密码学与非确定型图灵机 . 中国电子科学研究院学报 , 2008, 3(6): 558-562. 杨正瓴 . 第二类计算机构想 . 中国电子科学研究院学报 , 2011, 6(4): 368-374. YANG Zhengl ing ( 杨正瓴 ). A non-canonical example to support that P is not equal to NP . Transactions of Tianjin University, 2011, 17(6): 446-449. 相关链接： 郝克刚 教授《纠正对NP 问题的错误理解（3）-- 对一位网友文章的评论》 http://blog.sciencenet.cn/home.php?mod=spaceuid=506146do=blogid=530828 徐建良 教授《P对NP -- 与杨正瓴老师商榷》 http://blog.sciencenet.cn/./home.php?mod=spaceuid=66861do=blogid=551309 《A FULL PROOF to the P versus NP problem》 http://bbs.sciencenet.cn/home.php?mod=spaceuid=107667do=blogid=486692 里面有一些全文可以下载。 您有兴趣，可以直接跟我要相关的论文全文。 《 “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案》 http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=266338 《 Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）》 http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=106360
汉语是联合国官方正式使用的6种同等有效语言之一。请不要歧视汉语！ A FULL PROOF to the P versus NP problem “P对NP（P versus NP, P vs NP）”问题的一个“完全证明” 1 相关背景简介 （1）“P对NP（P versus NP, P vs NP）”问题的描述 “ The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time. ” 详见：《“P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案》， http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=266338 以及：《Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）》， http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=106360 The Clay Mathematics Institute 的原始描述： http://www.claymath.org/millennium/P_vs_NP/ . （2）什么是“完全证明” What is a “Full Proof” ？ The Mathematical proofs of a proposition must give the following three cases: (1) The proposition is valid, under some certain axiomatic systems; (2) The proposition is not valid, under other axiomatic systems; (3) The proposition can not be proved/decided, without the necessary designating axiomatic systems. A Full Proof requires that the three cases are all identified definitely. 详见：《什么是“完全的数学证明”？》， http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=83926 2 未来的可能做法 根据学术规范， 通常情况下，以下重复发表不属于一稿两 ( 多 ) 投： 1) 在专业学术会议上做过口头报告，或者以摘要或会议板报形式报道过的研究结果，但不包括以会议文集或类似出版物形式公开发表过的全文； 2) 对首次发表的内容充实了 x% 以上新数据的学术论文； 3) 有关学术会议或科学发现的新闻报道，但此类报道不应通过附加更多的资料或图表而使内容描述过于详尽； 4) 重要会议的纪要、有关组织达成的共识性文件再次发表； 5) 论文以不同或同一种文字在一种期刊的国际版本上再次发表； 6) 在非英文的本国期刊上发表的属于重大发现的研究论文在国际英文学术期刊再次发表； 7) 在内部资料发表后在公开刊物上再次发表。 本帖主要学术观点，以及《 第二类计算机构想 》等都是汉语的，根据以上规范： 计划将来形成英文的详细论证，再投英文的国际期刊。 3 1995年报告要点回顾 记 DTM 为确定型图灵机（ deterministic Turing machine ）； NDTM 为 “ 非确定型图灵机 ” （ non-deterministic Turing machine ）。 （ 1 ） “P 对 NP” 不能被直接证明。它实际上是 3 个问题的合成： ① 对于 NDTM ， P=NP ； ② 对于 DTM ， P ≠ NP ； ③ “ P 对 NP ” 具 有独立性，如果不指明在那种计算机理论里进行研究。 （ 2 ）对于 DTM ， P ≠ NP ，是通常研究的核心。 从数学研究的整体方法看， “ P 对 NP ” 是属于 “ 数 ” 的范围。既然在 “ 数 ” 的方法下没有获得明确答案，就应该转移到 “ 形 ” 的方法进行研究。 对于第一个 NPC ，即布尔可满足性问题（ Boolean Satisfiability Problem ， SAT ），不难发现，在图论模型下， 2SAT 一定是平面图， 3SAT 以及 4SAT 则可能包含 Kuratowski 图 K 3,3 ，是立体图。而 5SAT 可能包含 Kuratowski 图 K 5 和 K 3,3 ，也是立体图。 （ 3 ）在无穷化版本下， NPI 的存在性，就 是 “ 连续统假设 CH ” ：可数无穷基数 a 和连续统基数 c 之间是否存在一个其它的无穷基数。 4 其后的认识 （ 1 ）用旅行推销员问题（ Travelling Salesman Problem ， TSP ），可以比用 SAT 更直观地说明 “P 对 NP” 的关系。所有顶点度数为 2 的 TSP ，称为 2TSP 。显然， 2TSP 只能是一个回路，或者若干不相交的回路。因此 2TSP 是平面图。相反， 3TSP 或更高的各 TSP ，可能包含与 K 5 或 K 3,3 同胚的子图，不是平面图。 （ 2 ）无穷版本下的 NDTM （非确定型图灵机），可以不是平面图。 计划用英文投稿。 （ 3 ）概率意义下 的 “ 对于 DTM ， P ≠ NP ” ，即 “ 对于 DTM ， P ≠ NP 几乎处处（ almost everywhere ， a. e. ）成立 。 ” 计划用英文投稿。 5 “P对NP”完全证明的要点总结 （1）完全证明的结论 ① 对于 NDTM ， P=NP ； ② 对于 DTM ， P ≠ NP ； ③ “P 对 NP” 具有独立性，如果不指明在那种计算机理论里进行研究。 （2）对DTM，P ≠ NP的3类证明 ① 有穷形式下形转化的直接证明； 2TSP 是平面图。相反， 3TSP 或更高的各 TSP ，可能包含与 K 5 或 K 3,3 同胚的子图，不是平面图。 ② 无穷形式/版本下的证明，直接否证Cantor原本意义下的“连续统假设”； 字母表等为可数无穷时， DTM 仍为可数无穷；相反， NDTM 为连续统。 ③ 概率形式、有穷形式下的直接证明。 暂时不能公开，计划 用英文投稿。 6 相关报告与论文 《 My report and papers on "the P versus NP problem" (P vs NP) 》 http://bbs.sciencenet.cn/home.php?mod=spaceuid=107667do=blogid=483639 从 NP 结构到超级计算机分类理论 . 天津大学百年校庆研究生院研究生学术报告会（一等奖论文） , 和天津大学百年校庆自动化系学术报告会 , 1995 年 10 月 . From the hierarchy of NP to a classification of supercomputer. The Student Academic Symposium of Graduated School to Celebrate the 100th Anniversary of the Founding of Tianjin University, October, 1995. (An oral report in Chinese) 人类智能模拟的 “ 第 2 类数学（智能数学） ” 方法的哲学研究 . 哲学研究, 1999, 4: 44-50. Philosophical research on "the second class mathematics (intelligent mathematics)" for simulations of human intelligence. Philosophical Research, 1999, 4: 44-50. (in Chinese) 密码学与非确定型图灵机 . 中国电子科学研究院学报 , 2008, 3(6): 558-562. Cryptology and non-deterministic Turing machine. Journal of China Academy of Electronics and Information Technology, 2008, 3(6): 558-562. (in Chinese) 第二类计算机构想 . 中国电子科学研究院学报, 2011, 6(4): 368-374. Conception of the second class computer. Journal of China Academy of Electronics and Information Technology, 2011, 6(4): 368-374. (in Chinese) 里面有 1995 年报告（ ）的主要观点概述。 A non-canonical example to support that P is not equal to NP. Transactions of Tianjin University, 2011, 17(6): accepted. 支持 P 不等于 NP 的一个非规范例子（英文稿） . YANG Zhengling (杨正瓴). A non-canonical example to support that P is not equal to NP . Tra nsactions of Tianjin University, 2011, 17(6): 446-449. 现在已经刊出，2011-12-05后记。 “P对NP”难题研究的形转换新思路 ，中科院在线《科学智慧火花》，2011-08-30， http://idea.cas.cn/viewdoc.action?docid=1275 。 ———————————— 附录 ———————————— 《第二类计算机构想. 中国电子科学研究院学报, 2011, 6(4): 368-374》 内容截取如下： 真诚欢迎您的批评！假如上述内容还值得您批评！谢谢！ 该两页内容的图片格式.rar 该两页内容的pdf格式.pdf 2011 A non-canonical example to support P is not equal to NP.pdf 2011 第二类计算机构想 Conception of the Second Class Computer (in Chinese, ZL Yang).pdf 弱弱地问：有木有问题？
My reportand papers on "the P versus NP problem" (P vs NP) 杨正瓴, Zheng-Ling YANG, YANG Zhengling Abbreviations: NDTM, non-deterministic Turing machine; DTM, deterministic Turing machine; NPC, NP-complete; NPI, NP-Intermediate; CH, continuum hypothesis; TSP, traveling salesman problem. The FULL PROOF: The mathematical proofs of a proposition must give the following three cases: (1) The proposition is valid, under some certain axiomatic systems; (2) The proposition is not valid, under other axiomatic systems; (3) The proposition can not be proved/decided, without the necessary designating axiomatic systems. A FULL PROOF requires that the three cases are all identified definitely, because "Any proof is relative, since it is based on certain unprovable assumptions." http://eom.springer.de/P/p075420.htm (Encyclopaedia of Mathematics, Edited by Michiel Hazewinkel, an updated and annotated translation of the Soviet "Mathematical encyclopaedia") The essence of "the P versus NP problem": ① P = NP for a NDTM; ② P ≠NP for a DTM; ③ The “P vs NP problem” can not be proved/decided, without the necessary designating of a NTM or DTM. The keys of two sufficientproofs of "P ≠NP for a DTM": (1) 2SAT is a planar graph; 3SAT can be a non-planar graph, since it can have the Kuratowski graph K3,3. (2) Non-canonically, a maximal NDTM is the power set of DTM. If the "Axiom of power set" in ZFC (Zermelo–Fraenkel set theory with the axiom of choice) is accepted, then P ≠NP for a DTM. My relative report and papers: 从NP结构到超级计算机分类理论 . 天津大学百年校庆研究生院学术报告会（一等奖论文）, 和天津大学百年校庆自动化系学术报告会, 1995年10月. From the hierarchy of NP to a classification of supercomputer. The Student Academic Symposium of Graduated School to Celebrate the 100th Anniversary of the Founding of Tianjin University, October, 1995. (An oral report in Chinese) 人类智能模拟的“第2类数学（智能数学）”方法的哲学研究 . 哲学研究, 1999, 4: 44-50. Philosophical research on "the second class mathematics (intelligent mathematics)" for simulations of human intelligence. Philosophical Research, 1999, 4: 44-50. (in Chinese) 密码学与非确定型图灵机 . 中国电子科学研究院学报, 2008, 3(6): 558-562. Cryptology and non-deterministic turing machine. Journal of China Academy of Electronics and Information Technology, 2008, 3(6): 558-562. (in Chinese) 第二类计算机构想 . 中国电子科学研究院学报, 2011, 6(4): 368-374. Conception of the second class computer. Journal of China Academy of Electronics and Information Technology, 2011, 6(4): 368-374. (in Chinese) A non-canonical example to support that P is not equal to NP . Transactions of Tianjin University, 2011, 17(6): accepted. 支持 P 不等于 NP 的一个非规范例子（英文稿） . YANG Zhengling (杨正瓴). A non-canonical example to support that P is not equal to NP . Tra nsactions of Tianjin University, 2011, 17(6): 446-449. 现在已经刊出，2011-12-05后记。 “P对NP”难题研究的形转换新思路 ，中科院在线《科学智慧火花》，2011-08-30， http://idea.cas.cn/viewdoc.action?docid=1275 。 拟投英文稿2个，正在写作。 相关链接： 真傻 对 “ P 对NP（P versus NP, P vs NP） ”问题的思考，请看： “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案： http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=266338 Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）： http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=106360
IC50 versus EC50 The IC50 represents the concentration of a drug that is required for 50% inhibition of viral replication in vitro (can be corrected for protein binding etc). The EC50 represents the plasma concentration/AUC required for obtaining 50% of the maximum effect in vivo. http://www.fda.gov/ohrms/dockets/ac/00/slides/3621s1d/tsld036.htm IC50 From Wikipedia, the free encyclopedia Jump to: navigation , search The half maximal inhibitory concentration (IC 50 ) is a measure of the effectiveness of a compound in inhibiting biological or biochemical function. Often, the compound in question is a drug candidate. This quantitative measure indicates how much of a particular drug or other substance ( inhibitor ) is needed to inhibit a given biological process (or component of a process, i.e. an enzyme , cell , cell receptor or microorganism ) by half. In other words, it is the half maximal (50%) inhibitory concentration (IC) of a substance (50% IC, or IC 50 ). It is commonly used as a measure of antagonist drug potency in pharmacological research. Sometimes, it is also converted to the pIC 50 scale (-log IC 50 ), in which higher values indicate exponentially greater potency. According to the FDA , IC 50 represents the concentration of a drug that is required for 50% inhibition in vitro . It is comparable to an EC 50 for agonist drugs . EC 50 also represents the plasma concentration required for obtaining 50% of a maximum effect in vivo . Determination IC 50 of a drug Functional antagonist assay The IC 50 of a drug can be determined by constructing a dose-response curve and examining the effect of different concentrations of antagonist on reversing agonist activity. IC 50 values can be calculated for a given antagonist by determining the concentration needed to inhibit half of the maximum biological response of the agonist. IC 50 values are very dependent on conditions under which they are measured. In general, the higher the concentration of inhibitor, the more agonist activity will be lowered. IC 50 value increases as enzyme concentration increases. Furthermore depending on the type of inhibition other factors may influence IC 50 value; for ATP dependent enzymes IC 50 value has an interdependency with concentration of ATP, especially so if inhibition is all of it competitive . IC 50 values can be used to compare the potency of two antagonists. Competition binding assays In this type of assay, a single concentration of radioligand (usually an agonist) is used in every assay tube. The ligand is used at a low concentration, usually at or below its K d value. The level of specific binding of the radioligand is then determined in the presence of a range of concentrations of other competing non-radioactive compounds (usually antagonists), in order to measure the potency with which they compete for the binding of the radioligand. Competition curves may also be computer-fitted to a logistic function as described under direct fit. In this situation the IC 50 is the concentration of competing ligand which displaces 50% of the specific binding of the radioligand. The IC 50 value is converted to an absolute inhibition constant Ki) using the Cheng-Prusoff equation (see Ki). IC 50 and affinity IC 50 is not a direct indicator of affinity although the two can be related at least for competitive agonists and antagonists by the Cheng-Prusoff eqtn. where Ki is the binding affinity of the inhibitor, IC 50 is the functional strength of the inhibitor, is substrate concentration and km is the affinity of the substrate for the enzyme.Whereas the IC 50 value for a compound may vary between experiments depending on radioligand concentration, the K i is an absolute value. K i is the inhibition constant for a drug; the concentration of competing ligand in a competition assay which would occupy 50% of the receptors if no radioligand were present. Half maximal effective concentration From Wikipedia, the free encyclopedia (Redirected from EC50 ) Jump to: navigation , search The term half maximal effective concentration ( EC 50 ) refers to the concentration of a drug, antibody or toxicant which induces a response halfway between the baseline and maximum after some specified exposure time. It is commonly used as a measure of drug potency and toxicity . The EC 50 of a graded dose response curve therefore represents the concentration of a compound where 50% of its maximal effect is observed . The EC 50 of a quantal dose response curve represents the concentration of a compound where 50% of the population exhibit a response . It is also related to IC 50 which is a measure of a compound's inhibition (50% inhibition). For competition binding assays and functional antagonist assays IC 50 is the most common summary measure of the dose-response curve. For agonist/stimulator assays the most common summary measure is the EC 50 . Concentration measures typically follow a Sigmoidal curve, increasing rapidly over a relatively small change in concentration. The point at which the effectiveness slows with increasing concentration is the IC 50 . This can be determined mathematically by derivation of the best-fit line. However, it is more easily observed from a graph and estimated rather than through complex calculus equations . Equation Many different equations can be used to derive an EC 50 . One possible function is: Y = Bottom + (Top - Bottom)/(1 + (X/EC 50 ) (Hill coefficient) ) where Y is the observed value, Bottom is the lowest observed value, Top is the highest observed value, and the Hill coefficient gives the largest absolute value of the slope of the curve. And an alternate form of the equation is: Y = Bottom + (Top - Bottom)/(1+ 10 ((Log(EC 50 )-X) * (Hill coefficient)) ) Limitations The effects of a stressor or drug generally depend on the exposure time. Therefore, the EC 50 (and similar statistics) will be a function of exposure time. The exact shape of this time function will depend upon the stressor (e.g., the specific toxicant), its mechanism of action, the organism exposed, etcetera. This time dependency hampers the comparison of potency or toxicity between compounds and between different organisms. LC50：半数致死浓度，引起受试对象50%个体死亡的药物浓度。 IC50：半数抑制浓度 ，一种药物能将细胞生长、病毒复制等抑制50%所需的浓度。 EC50：半数效应浓度，引起受试对象50%个体产生一种特定效应的药物剂量。 What is the difference between an IC50 and an EC50 and an ED50? FAQ#1332 The differences are just nomenclature, and not conceptual. EC means effective concentration, and is used for dose-response curves that go up hill. IC means inhibitory concentration, so is used for dose-response curves that go downhill, because the drug inhibits a response. In both cases, C stands for concentration. In some experiments, you vary the administered dose, but don't know the effective concentration. In these cases, the midpoint is called the ED50.
标签: versus
