Nature的“道歉”发表后，科学网可说是“举网欢腾”。但是读了原文之后，不禁心生疑惑，Nature 的“道歉”究竟说了些什么？下面是Nature的原文，我的翻译和评论。 EDITORS’ NOTE (updated 6 August 2012) This article has drawn an extraordinary level of outraged response. The volume of comments has been so great that our online commenting system is unable to cope: it deletes earlier posts as new ones arrive. We much regret this ongoing problem. The disappearance of some cogent responses to the story has fuelled suspicions that Nature is deliberately censoring the strongest criticisms. This is absolutely not the case: Nature welcomes critically minded discussion of our content. (We intentionally removed only a few comments that violated our Community Guidelines by being abusive or defamatory, including several that offensively stereotyped the many Chinese readers who commented on the story.) 本文引来了异乎寻常之多的义愤填膺的回应。评论的数量是如此之大以至于我们的在线评论系统难以承受，在新的评论涌入时删除了旧的评论。对这个仍然存在的问题我们非常抱歉。一些很有说服力的对原文的批评的消失引起了怀疑：Nature有意删除了最强烈的批评意见。这绝对不是事实：Nature 欢迎对我们文章内容的批判性讨论。（我们有意删除了一些辱骂和诽谤性的评论，包括几个令人厌恶的对中国读者怀有偏见的评论） *** 博主评论： Nature 对于一个技术问题表示了歉意，顺便表扬了一下自己的公正性,同时澄清了对Nature公正性的怀疑。 *** Many of the commenters have questioned why we changed the original subtitle of the story from “‘Performance profiling’ could help catch sports cheats” to “‘Performance profiling’ could help dispel doubts”. The original version of the title was unfair to the swimmer Ye Shiwen and did not reflect the substance of the story. We regret that the original appeared in the first place. We also regret that the original story included an error about the improvement in Ye’s time for the 400-metre individual medley: she improved by 7 seconds since July 2011, not July 2012. We have corrected the error. 许多评论者问我们为什么把原来的新闻标题“‘成绩曲线’能够帮助我们发现体育运动中的欺骗行为”改成了“‘成绩曲线’能够帮助我们驱散怀疑”。原来的标题对游泳选手叶诗文是不公平的，也没有反映新闻的实质内容。首先，我们为原来的标题表示道歉。我们也为原来的新闻中包含的一个错误about the improvement in Ye’s time for the 400-metre individual medley: she improved by 7 seconds since July 2011, not July 2012表示道歉。我们已经改正了这个错误。 *** 博主评论： Nature承认新闻中有一个数据错误，并为此表示道歉；除此之外，Nature暗示新闻的实质内容并不错，只是原始的标题有不公正的地方，也为此道歉。Nature的道歉就这么多了。 *** We apologize to our readers for these errors, and for the unintended removal of comments because of technical issues with our commenting system. Below we reproduce one of the most thorough and thoughtful of the hundreds of responses we received. Beneath it, we continue with our response. 。。。。。。（无需翻译）。。。。 EDITORS’ NOTE (continued) The news story was triggered by a debate that was already active, concerning the scale of Ye Shiwen’s victory. Such debates have arisen over many outstanding feats in the past, by athletes from many countries, and it is wrong to suggest, as many of the critics do, that we singled her out because of her nationality. 关于叶诗文的胜利的争论早已非常活跃，此新闻的灵感就是由此来的。来自许多国家的表现特别突出的许多运动员早就引起了这样的争论。许多批评者认为我们单单选择了叶诗文是因为她的民族，这种观点是错误的。 *** Nature说，虽然我们提到叶诗文，但并不是因为她是中国人，所以这篇新闻与种族和政治无关，请不要对号入座。 *** The story’s intention as an Explainer was to examine how science can help resolve debates over extraordinary performances, not to examine those performance statistics in detail. Several analyses done by others convinced us that it was fair to characterize Ye’s performance as ‘anomalous’ — in the sense that it was statistically unusual. But we acknowledge that the combination of errors discussed above and the absence of a more detailed discussion of the statistics (which with hindsight we regret) gave the impression that we were supporting accusations against her, even though this was emphatically not our intention. For that, we apologize to our readers and to Ye Shiwen. 本新闻的意图是考察科学怎样能帮助解决关于非同寻常的运动成绩的争论，而不是详细考察这些成绩的统计学。其他人做的几个分析使我们确信，用“反常”-统计上非同寻常-来描述叶诗文的表现是公正的。但是我们认识到，由于上面提到的几个错误的组合，以及缺少统计学上更加详细的讨论（事后我们很抱歉），此事给了大家我们支持指控叶诗文的印象，虽然这绝不是我们的本意。对此我们向读者和叶诗文表示道歉。 *** Nature说，本新闻在科学上是正确的，叶诗文的表现就是科学上的“反常”。不过“反常”不等于“兴奋剂指控”，你们理解错了。无论如何，我向你们表示道歉。 *** 博主后记： 我没有读过Nature那篇令国人如此激动的原文，不敢妄评。 这次风波唯一能够证明的，就是Nature在许多国人特别是科学网的许多博主的心目中，有很崇高的地位。国内外媒体上天天都有成千上万篇大骂中国人的文章，从来没有引起科学网的签名抗议。
Non-professionals are required to write their stories with each word starting with a letter "N", whileprofessionalsare required towrite their stories with each word starting with a letter "P". Is there any surprise that the NP problem is leftunsolvable?
Can the complex motions in fluid, such as Brownian motion and diffusion, be described with the exact solution of the motion equations of fluid? This problem is closely related to the famous " Millennium Prize Problems " established by the Clay Mathematics Institute of Cambridge, Massachusetts，for celebrating mathematics of new millennium. One of them is about the Navier-Stokes equation. This problem was introduced shortly and vividly in the website of the Clay Institute as follows: Waves follow our boat as we meander across the lake, and turbulent air currents follow our flight in a modern jet. Mathematicians and physicists believe that an explanation for and the prediction of both the breeze and the turbulence can be found through an understanding of solutions to the Navier-Stokes equations. Although these equations were written down in 19th Century, our understanding of them remains minimal. The challenge is to make substantial progress toward a mathematical theory which will unlock the secrets hidden in the Navier-Stokes equations. Obviously, one of the possible explorations to the this problem is to try to give an exact solution to the Euler equation (which is the simplest case of Navier-Stokes equations) for describing some complex fluid motions. In the past thirty years, several exact solutions of such kind were given, such as in , , and . But these solutions usually need some complex and unnatural external force in the Euler equation, i.e., the corresponding complex motions were driven by the complex and unnatural external force (here, the "unnatural external force" means a non-potential force). So, these solutions are somehow not quite satisfactory. From 2006 to 2008, this problem was also studied by me and my graduate students Weiwei Yu and Minghui Liu. Based on the "pseudo-potential" conception proposed by Weiwei Yu, a kind of exact solution of the Euler equation was found out. This kind of exact solution contains two arbitrary given functions and three arbitrary given parameters, and the external force of the corresponding Euler equation could be zero or any given potential force. Based on the choice of the two functions and three parameters contained in the solution, and based on the KAM theory and Melnikov Method, it is proven that the Brownian motion and diffusion of the fluid can described by the chosen exact solution. The concrete exact solutions and the sketch of the related proofs are introduced in my blog paper A Series along the Nature and Beauty in Chinese. The exact solutions and the obtained second order Melnikov function are also listed on the attached pdf file Main Mathematical Formulae in English. Main Mathematical Formulae.pdf To show the complex motion (diffusion), an animation (click on the animation to watch it) was made with the software Mathematica. In this animation, 40000 fluid particles are initially distributed to four small circles, and the four groups of particles are each dyed with a different color, so that each circle has their own unified color. The animation shows how the 40000 particles move according to the chosen exact solution, and how the four colored circles develop into four different closed curves following the fluid particles on it. It is a well known fact that if infinitely many particles are continuously distributed on the four circles, following the motions of the fluid particles, the shapes of the four circles will develop into four closed curves (homotopic to the original four circles), while the areas surrounded by them are maintained respectively, and the four closed curves will never intersect each other. This means the true diffusion (or osmosis) can not really happen if the continuity of the curves is not destroyed. However, for a practical fluid, the fluid particles are always with finite number, no matter how large the number is. So, each circles are formed with only a finite number fluid particles. When the "pseudo-continuous" curves are stretched and deformed drastically, the "continuity" of these curves will be destroyed, obviously, and the diffusion (or osmosis) will really happen between the particles distributed on the four closed curves, shown this way by the animation. The velocity field described by the chosen exact solution used for the animation is periodic both in time and in the coordinates of the two dimensional plane. It is proven by calculation that the mean value of the velocity over time and over space is zero, while the mean value of the square of the velocity is a positive number if the motion exists. Clearly, the larger the mean value of the square of the velocity is, the stronger the complex motion of the fluid is. Therefore, if the period of time and period of space are small from the view point of macro-scope, then the exact solution obtained can be treated as a module of static water with temperature which is proportional the mean value of the square of the velocity. References: T.H.Solomon and J.P. Gollub, Chaotic particle transport in time-dependent Rayleigh-Benard convection , Physical Review A. Vol.38 No. 12, (1988) 6280-6286 S. Wiggins, The dynamical systems approach to Lagrangian transport in oceanic flows , Annu. Rev. Fluid Mech. 37, (2005) 295–328. N. Malhotra and S. Wiggins, Geometric Structures, Lobe Dynamics, and Lagrangian Transport in Flows with Aperiodic Time-Dependence, with Applications to Rossby Wave Flow ,J. Nonlinear Sci. Vol. 8: pp. 401–456 (1998) Author: Keying Guan (Science College, Beijing Jiaotong University) email: keying.guan@gmail.com
题材如下，写议论文。 美国老师以为大多会选择继续手术，因为上英语课的多是东亚几个非英语国家的学生。 确实算不错的论题。 你是怎么想的呢？ －－－－－－－－－－－ The Twin Problem... You are a highly skilled surgeon with a flourishing practice. You know you are very good at what you do and have earned the respect of your patients. ne day a Mr. and Mrs. Waterhouse come to see you. They are obviously very upset, and tell you they have a problem of life and death and need your help. The Waterhouses explain that they are the parents of 14-year-old twin girls named Irene and Meg. Some years ago Irene contracted a disease of the kid- neys, and she has been seriously ill ever since. Her kidneys are now so badly damaged that unless she receives a kidney transplant she will surely die within three months. Irene is a charming and open girl, full of vitality and intelligence. She is studying piano, and is so good that her teacher feels sure she will have a most successful professional career—if she lives. The parents tell you—as you already know—that the only kidney transplant which will be successful is one from Irene’s identical twin. All other kidney transplants are universally unsuccessful because of rejection by the recipients of the “foreign” tissue. Only Meg’s kidney can save Irene’s life. You also know that a kidney transplant between twins is a relatively safe operation. There is some risk, of course, as there is with any major surgery, but it is minimal. Both the donor and the recipient can get along on one kidney apiece. The obvious solution is for you to transplant one of Meg’s kidneys to Irene, and that is what Mr. and Mrs. Waterhouse ask you to do. But, they tell you, there is a serious problem. Meg has flatly refused to agree to the operation. Unlike her sister, Meg is depressed, socially backward, and shy. Her parents have focused on Irene’s illness and her musical achievements, and Meg feels profoundly rejected. Meg’s parents have told her about the urgent need for the transplant. They have explained that Irene will die unless she is given one of Meg’s kidneys. But Meg says she has always hated Irene, who has received much more love and attention than she has, and she—Meg—will certainly do nothing whatsoever to prevent Irene from dying. Every possible device has been used to make Meg change her mind, including extensive psychiatric treatment, but without success. In desperation, say the Waterhouses, they have come to you for help. In the state in which you practice you are permitted to operate on a person under the age of 18 if his or her parents consent to the operation. The patient, as a minor, has no legal rights in the matter. Mr. and Mrs. Waterhouse say they have decided to ask you to go ahead and perform the operation over Meg’s objections in order to save Irene’s life. They know you are the best possible surgeon, and say they will do whatever you decide—but they plead with you to decide to operate.
http://scienceblog.com/ New twist on ancient math problem could improve medicine, microelectronics Chimpanzee fools humans by hiding ammo Free-floating planets in the Milky Way outnumber stars by factors of thousands BMP8B stimulates brown fat to burn calories Enzyme corrects more than 1 million faults in DNA replication Could animal hair, feathers lead to clues to restore human fingers and toes? U.S. fattest country in the world Tsunami builds a vibrant beach If diners must wait, increase their comfort Stanford study shows no evidence that international health aid is wasted New Facebook Page To Move Kids from Facts to Questions The paradox of scientific research The Bacon Gene Safer sex work spaces reduce violence and HIV risks for street-involved women New site of potential instability in West Antarctic Ice Sheet
For what the UW charges each out-of-state student, it ought to provide better services. It messed up two out of three bills, and ended up charging the student the so-called LTF (late transaction fee?) each time. Look, there is room to spell out LTF, unless you intend to fool the recipient, which apparently worked.
汉语是联合国官方正式使用的 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
Abstract: hort-term earthquake prediction has always been a very difficult problem in geology, 15 this article pre-displacement, pre-established short-term break for the earthquake prediction based on the theory becomes completely abandoned to form the basis of earthquake prediction method, short-term earthquake prediction is a theoretical breakthrough. Key words: Mechanics; earthquake,;short-term forecasting,;pre-displacement; pre-fracture 摘要： 地震短期预报历来是一个十分困难的地质学问题，本文以预位移预断裂为依据对于短期地震预报进行了理论思考，一旦该理论被实践所证明，将会是地震短期预报的一次理论突破。 关键词 ：固体力学；地震；短期预报；预位移；预断裂 预位移预断裂短期地震预报数学方法探析.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
《How To Choose a Good Scientific Problem》 Abstract: Choosing good problems is essential for being a good scientist. But what is a good problem, and how do you choose one? The subject is not usually discussed explicitly within our profession. Scientists are expected to be smart enough to figure it out on their own and through the observation of their teachers. This lack of explicit discussion leaves a vacuum that can lead to approaches such as choosing problems that can give results that merit publication in valued journals, resulting in a job and tenure. 个人点评： 我认为此文精华在下图 a rule for new students and postdocs: Do not commit to a problem before 3 months have elapsed.
For new readers and those who request to be “ 好友 good friends”please read my 公告 栏 first. First of all, a word of explanation about the title: 1. Decentralized – By this word, I mean the absence of an all wise and all knowing supreme being which governs everything that go around in an idealized world for the best of all possible purposes. In this real world, events take place via the interactions of individuals, organizations, and countries each pursuing their own agenda and interest. 2. Control and Optimization – By these two words which I use in the colloquial sense to mean that human civilization always strive for “improvement” though not always successfully. This is a fundamental desire. #1 and #2 certainly reflect the situation in the real world. . Now I want to explain conceptually why this is hard, very hard, to do. In the process I hope to explain using very simple terms as to the “what” and “why that constitute an impossibility theorem. In my earlier blogs you may have read my mention of the so-called “Witsenhausen Problem”. This is a problem made famous by Hans Witsenhausen, a Bell Laboratory researcher in 1968 to illustrate the difficulty with information and coordination (the issue of who know what when and dynamic team theory. If you google or bing it you will get over 1000 reference to this problem ). It is a problem of the SIMPLEST kind with all the right mathematical assumptions such as linearity, convexity, Gaussian noise, etc. involving only two decision variables. You have a constant (which is a sample of a gaussian random variable) to eliminate or cancel. The first decision maker, DM1, knows exactly the value of this constant, but his action is costly. Thus, it costs something for him to eliminate the constant (reduce it to zero). The second decision maker, DM2, who acts after the first decision maker incurs no cost to act, but he does not know what DM1 knows. He only has a noisy observation of the resultant value of the unknown (to him) constant value plus any effort on the part of DM1’s attempt to cancel this constant. Thus he cannot cancel what remains exactly if he uses the noisy observation. The un-canceled leftover will incur a cost. The problem is what should the two decision maker jointly do so that resultant performance (cost to cancel in part or in whole by DM1 plus the leftover un-canceled portion due to uncertainty and the action of DM2) is at a minimum . Note the problem will be trivial not even qualify to be an exercise in an undergraduate control/optimization course if the two decisions are under the control of one decision maker – the centralized case (we can even let the first decision’s information be noisy also. The optimal solution is well known to every student in such courses). But this simple change of different decision maker having different and non-inclusive information made all the difference. Witsnehausen did not solve the problem he thus posed. But showed a number of surprising things. Among them: What everyone expect to be the answer – a linear proportional solution- is not optimal A much better nonlinear solution, though still not optimal, exists. This is highly surprising at the time. In the ensuing 40+ years (1968-2009), a large number of people, including myself spend enormous number of hours using rather advanced technical theory trying to advance the solution to this so-called W-problem resulting in many published papers on different aspects of this simplest problem. In 2002, my student and I finally published a numerical solution of the Witsenhausen problem with a conceptual explanation that captures the essence of the problem. We claimed that we have exhausted all the ideas associated this problem and any further improvement can only be numerical (for example using more significant number of digits in computation, or a better search algorithm). Since 2002, several other people have worked on this problem (including someone just last month) but no one has invalidated our claim. Thus, you can say that the last word probably has been said on it. But why such an apparently simple problem took 40+ years and many scholars’ time? Now let me explain the essence of this simple problem in an even simpler way without any advanced mathematics. Once understood, readers will begin to appreciate why decentralized control and optimization (in plain language – coordinate actions to work for the common good) is very hard in the best of circumstances. Once you add in human frailties, politics, and other vices, a perfect world is impossible for all practical purposes. Think back to the W-problem.as described above. It is clear unilateral action by either decision maker (for DM1 to simply cancel out the constant regardless of the cost or for DM2 to treat the noisy observation as true value and cancel accordingly) is not going to be the best course of action. Thus, they need to cooperate and each does a bit of work. The expected linear solution simply does a proportional compromise which is better than unilateral action by either one. But you can do better. The following are clear: For DM1 you wish to use as small an effort as possible in changing (canceling in whole or in part) the value of the constant since it is costly for him to act. If the constant is either one of two possible known values separated far apart comparing to the size of the noise, then canceling by the DM2 should be easy. Because even with noise, you can be very certain which one of the two values the constant has and cancel with no cost accordingly. From these two considerations, a nonlinear scheme emerges. Let DM1 observe the constant exactly and then proceed to change (cancel) the value of the constant to either one of two pre-agreed-on positive or negative value, say +or – C. DM2 then observes with noise either plus or minus C and can be pretty certain even under noise which one it is and cancel it out completely. Now of course when the particular noise sample is very large, mistake in cancellation can still occur. Similarly, when the value of the constant is very different from + or – C, the cost of moving to these values can be high. But the probability of these rare event happening are very small. Thus, on expected value basis, this nonlinear scheme works better than any sort of compromise using linear proportional methods. In effect, DM1 is signaling to DM2 (Nobel economics prize 2002 to Michael Spence on market signaling is based on similar idea). Finally, once you can use one pair of pre-agreed-on values, there is nothing wrong and every thing to gain by considering more than one pair of pre-agree-on values. More values will enable DM1 to choose the nearest value in order to minimize the cost moving the value of the constant. However, more pre-agreed-on values will complicate the problem for the DM2. He will have more chance of making mistakes because of observation noise when trying to guess which one of the many possible values DM1 has move the constant value to. Thus, there is a limit and tradeoff on the number and value of these pre-agreed-on points. For any given numerical example, we can perform a brute force search to solve the problem which is still computational intensive but doable (Note 1). This was what we did in 2002. It took 30-40 years before we realized the simple insight in this paragraph . Anyway, the above discussion points out the complexity of coordination even in the simplest problem between two decision makers. When you come to the real world where there are many interacting decision makers and vairables, much more complex dynamics and uncertainties, the resultant exponential growths adds MANY MORE ORDERS of difficulty and complexity. Thus, the popular slogan of think globally and act locally is much easily said than done . So far our discussion of complexity and difficulty is purely technical. We have not brought in other non-quantifiable and softer issues such as human frailty, emotion, nationalism, and politics that always intrude in the real world. What we generally do instead is iteratively tries to improve locally in the short term, and hope for the best globally and for the long term. You can also say that throughout history human beings by way of different types of government and systems try to solve or improve on the solution to this basically impossible dream. It is actually relatively amazing we do as well as we have done so far. But can our luck hold forever? Don’t you sometime wish for an all wise and benevolent dictator to decide everything? (Note 1. Actually because of the quadratic nature of the formula used to measure cost, there is an additional bit of extra that can be squeezed out of the problem by introducing a very small perturbation on the various pre-agreed-on points. But this is conceptually a detail dependent on the particular criterion used and not central to the major points of the discussion. Mathematically, however, such issues confused the research in earlier years which emphasized analytics of rather than the physical insight of the problem as explained above)
The Traveling Salesman Problem and Its Variations Series: Combinatorial Optimization , Vol. 12 Gutin, Gregory; Punnen, Abraham P. (Eds.) 2007, XVIII, 830 p., Softcover ISBN: 978-0-387-44459-8 Springer出版，非常全面系统地介绍了旅行商问题及其各种研究技术，下面是该书的About。后面有免费下载网址。 This volume, which contains chapters written by reputable researchers, provides the state of the art in theory and algorithms for the traveling salesman problem (TSP). The book covers all important areas of study on TSP, including polyhedral theory for symmetric and asymmetric TSP, branch and bound, and branch and cut algorithms, probabilistic aspects of TSP, thorough computational analysis of heuristic and metaheuristic algorithms, theoretical analysis of approximation algorithms, including the emerging area of domination analysis of algorithms, discussion of TSP software and variations of TSP such as bottleneck TSP, generalized TSP, prize collecting TSP, maximizing TSP, orienteering problem http://www.ebookee.com.cn/The-Traveling-Salesman-Problem-and-Its-Variations_147149.html
标签: Problem
