Stack Exchange是全球最大的问答网站之一(注),其中的“Computer Science”版面有很多关于算法理论诸问题的讨论,我们加入了其中一个质疑NP流行定义问题的讨论,摘出部分对话与大家分享,希望有兴趣的网友也能参加!这是网址: http://cs.stackexchange.com/questions/1887/why-isnt-this-undecidable-problem-in-np ,和 讨论的完整版: stackExchange1.pdf 此外,我们准备将科学网博客中关于NP的讨论介绍给国际同行,最近也有友人询问博文的英语版,推荐给在美国读计算机理论课程遇到困难的孩子看。所以,我们希望将这里的博文双语化,若有网友能协助一起工作,将感谢不尽! ****** BlueRaja - Danny Pflughoeft提问 :Why isn't this undecidable problem in NP?(为什么这个不可判定问题不在NP类里?) Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is yes have verifiable in polynomial time by a deterministic Turing machine. A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time. Now consider the following problem: Given a Diophantine equation, does it have any integer solutions? Given a solution, it's easy to verify in polynomial time that it really is a solution: just plug the numbers into the equation. Thus, the problem is in NP. However, solving this problem is famously known to be undecidable! (Similarly, it seems the halting problem should be in NP, since the yes-solution of this program halts at the N-th step can be verified in N steps.) Obviously there's something wrong with my understanding, but what is it? Yu Li(柳渝) :We think that the dilemma you raised about Diophantine equation is very significant, because it reveals something abnormal in the current definition of NP : - A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time. Concerning the definition of NP, it can be traced to the 60’s, where a great number of applicable and significant problems were discovered for which no polynomial algorithms could be found to solve them, in order to recognize these problems from those problems solvable in Polynomial time (P), the concept of NP was put out. However, the current definition of NP as verifiable in polynomial time confuses NP with P, because a problem in P is also verifiable in polynomial time. In another word, such definition leads to the loss of the essence of NP, « nondeterminisme ». Consequently, it causes serious ambiguities in understanding NP, for example, your dilemma : by nature the problem of Diophantine equation is undecidable; but by the definition of NP, it is decidable, … In our opinion, the difficulty in solving « P versus NP » lies firstly at cognition level, so if we hope to get an insight into « P versus NP », we need at first to question : What is NP? David Richerby :This seems to be an opinion piece about the definition of NP, not an answer to the question. The definition of NP is just fine. It doesn't confuse P with NP; rather, it acknowledges that P is a subset of NP. To me, it would be very unnatural if P were not a subset of NP. NP is a class of problems that can be solved within certain resource bounds. That necessarily includes a whole bunch of easy problems (P) that can be solved without coming close to the limit of the resources available. Yu Li(柳渝) :P and NP have the common property of « certificate verifiable in polynomial time » , but this property is not the essence of NP. If this property is used to define NP, then P is a subset of NP, and NP has P as its subset (decidable) and itself (undecidable). Therefore, one would wonder whether NP is decidable or undecidable? Just like the above dilemma : whether is Diophantine equation undecidable or decidable? So my answer is to suggest to investigate this dilemma from the view of the definition of NP: verifiable, undecidable is unverifiable! 注: -维基对Stack Exchange的简介: Stack Exchange是一系列问答网站,每一个网站包含不同领域的问题。这些网站参考Stack Overflow,一个关于程序设计的问答网站,也是Stack Exchange的第一个成员。如同Stack Overflow,这些网站使用声望奖励系统,用户对问题和答案进行投票,并影响用户声望。声望系统使这些网站可以自我控制。 -介绍Stack Exchange缘起的文章:全球最大的问答网站之一,Stack Exchange如何养成( http://www.huxiu.com/article/112013/1.html ) -分析Stack Exchange成功经验的文章:StackExchange和它的游戏规则( http://andnot.farbox.com/post/ke-yan-bi-ji/stackexchangehe-ta-de-you-xi-gui-ze )
Why Walking is benefical to your overall health? My personal point of view Many people believe that walking is good for improving your overall health condition, why? my understanding of this is that walking can help the circumfluence of your blood in lower limbs back to your right atrium, and therefore force them to participate in exchange of oxygen through lung circulation. 静脉血压 静脉血压是指静脉血管血压或左右心房不部位的血压,一般右心房(肢体回心静脉血)为5mmHg,左心房(肺部来的动脉血)为8mmHg, 比动脉血压120mmHg-80mmHg低16-24倍。因此,静脉血血流缓慢。 肺部血压: 通常情况下,静息状态的肺动脉压为15 mm Hg ,肺部毛细血管血压增高,则会出现肺部高压,如果血压高出20 mm Hg,会出现肺间质部位水肿,如果高出25 mm Hg则会出现肺积水(水肿) 因此,这种情况决定了你必须通过增加下肢压力迫使静脉血向右心房回流,增加回心血量,促进肺循环。
演化经济学的研究从凡勃伦开始,就和制度经济学形成了一定的联系。由于演化经济学击中了主流经济学静态化缺陷的要害,在各个经济学研究方向都具有重要的影响,如:微观经济学的选择模型、宏观经济学的经济周期模型等的理论基础。 演化经济学名称虽新,但和经济学不同的学派都具有一定的历史渊源,具有悠久的研究历史。从方法论特点看,演化经济学的研究与奥地利学派具有一定的有机联系。 奥地利学派研究主要强调的“市场过程”研究,是强调经济动态过程研究的主要流派,研究的是市场经济的重要动态现象,不是空谈经济的演化,而是建立在实实在在的研究对象之上,容易建立经济模型进行研究,相对容易取得一定的实际结果。 奥地利学派的研究进展主要体现在对交换模型的研究: The exchange paradigm : Where to now ? 但迄今还没有突破性成果问世。 奥地利学派不注重博弈理论研究,而强调交换理论研究,对于演化经济学的理论基础研究具有的启示是:演化博弈论对于演化经济学的作用,可能并不比市场交换过程中的讨价还价理论对于演化经济学的作用大。
I am wrapping up my visit at CAS/IAP, my third stop in China during this trip. Every place I have been to during this trip, I feel so welcomed. I wish I could work at each of these places two weeks at a time every six months. We will see.
Ms. Ref. No.: AGRFORMET-D-11-00606R2 Title: Interannual variability of net carbon exchange is related to the lag between the end-dates of net carbon uptake and photosynthesis: evidence from long records of two contrasting forest stands Agricultural and Forest Meteorology Dear Wu Chaoyang, I am pleased to inform you that your revised manuscript, AGRFORMET-D-11-00606R2, Interannual variability of net carbon exchange is related to the lag between the end-dates of net carbon uptake and photosynthesis: evidence from long records of two contrasting forest stands, by Wu Chaoyang, Ph.D; Jing M. Chen; Alemu Gonsamo; David T. Price; T. Andrew Black; Werner A. Kurz, has been accepted for publication in Agricultural and Forest Meteorology. It has been sent to Elsevier Science Ireland and further communication will be with them. You will receive a copyright transfer form from Elsevier. You will also receive page proofs in due course which must be returned promptly. You will also receive some free reprints of the article after publication. Prior to publication, you will be sent an order form and price list for additional reprints. Please note that it is possible to track the status of your paper on the Author Gateway at http:// www.elsevier.com/trackarticle. We are pleased to publish this interesting and informative paper. We of course would be happy to consider for publication other relevant works. Please keep us in mind. Sincerely yours, Timothy J Griffis, Ph.D. Associate Editor Agricultural and Forest Meteorology
与敖平继续讨论统计物理问题【5】 From: hqian@u.washington.edu 11:35 PM (9 hours ago) to me, Ping, Ping, Ping Hi, Ao Ping, Thanks Chen Lao Shi for introducing me to this email exchange; I am gland to know Professor Fang. I have one quick comment: Frank Kelly of Cambridge University (who was just elected into US NAE this year as a foreign member) has been working on a stochastic approach to network for many years. In some sense, he is one of the 先行者. http://www.statslab.cam.ac.uk/~frank/ In 1979, he already published a book http://www.statslab.cam.ac.uk/~frank/rsn.html in which the issue you have emphasized constantly, the issue of detailed balance, has been extensively discussed. The Markov network approach (both as process and as Gibbs measure of interacting systems) is very much in the same spirit as your Darwinian dynamics. It puts a dynamics on the structure. Best wishes to you all, Hong. Fwd: comments on Prigogine type approach to nonequilibrium processes-II aoping@sjtu.edu.cn 10:52 AM (26 minutes ago,2012\3\16) to me ----- 转发的邮件 ----- 发件人: "Jin Wang" jin.d.wang@gmail.com 收件人: aoping@sjtu.edu.cn 抄送: hqian@u.washington.edu 发送时间: 星期四, 2012年 3 月 15日 下午 9:30:06 主题: Re: comments on Prigogine type approach to nonequilibrium processes-II Ping, It is great that people in China are catching up. In fact, I believe the future of development (at least a significant part) will be in China. Cheers! Jin Sent from my iPad On Mar 15, 2012, at 6:28 AM, aoping@sjtu.edu.cn wrote: Here is a second one. Thanks. Ping ................................................................
若你在VirtualBox里的RHEL5里安装GreenPlumn单节点版本时,当执行到: 5. Run the gpssh-exkeys utility to exchange ssh keys for the local host: $ gpssh-exkeys -h 127.0.0.1 会出现如下错误: $ gpssh-exkeys -h 127.0.0.1 Traceback (most recent call last): File /usr/local/greenplum-db/./bin/gpssh-exkeys, line 522, in module (primary, aliases, ipaddrs) = socket.gethostbyaddr(hostname) socket.gaierror: Name or service not known 解决办法是: 切换到root用户,执行 # hostname localhost 既可解决。 当然上面只是临时解决,若想通过配置文件 二:修改linux主机的配置文件/etc/sysconfig/network 和 /etc/hosts 1.修改/etc/sysconfig/network里面的主机名字。 # vi /etc/sysconfig/network NETWORKING=yes HOSTNAME=localhost 参考: http://hchmsguo.iteye.com/blog/1256315 http://www.uini.net/2011/04/greenplumsne-error-socket-gaierror-errno-3-temporary-failure-in-name-resolution.html 加我私人微信,交流技术。
My Comment on ICTSD (Geneva)news: Pressure on China Currency, Subsidies Builds inWashington (11th Oct.2011) Luan Xinjie (China) 14th October 2011 at 01:48 What I want to say is that the currency exchange rate is indeed a macroeconomic issue, as stated by Director-General Pascal Lamy. The US Senate’s currency legislation is rather too simple for settling its huge trade deficitwith solely keeping sight on Chinese Yuan (Renminbi),which is like asserting “I have repaired my house” after hammering a single nail. In fact, the definition of so-called “currency manipulation” in China should be replaced by a statement of "taking no powerful action against Renminbi’s stability", and more seriously, the US Senate is teaching Chinese how to use the exchange rate to promote its exportation.
SCIENCE-BUSINESS EXCHANGE May 13 2010, Volume 3 / Number 19 Visit Science-Business eXchange online to browse the journal. Now available at http://links.ealert.nature.com/ctt?kn=84m=34883478r=Mzg0ODUxNzc3MQS2b=2j=NzM2NzU3MjkS1mt=1rt=0 Please note that you need to be a subscriber to enjoy full text access to Science-Business eXchange online. To purchase a subscription, please visit: http://links.ealert.nature.com/ctt?kn=17m=34883478r=Mzg0ODUxNzc3MQS2b=2j=NzM2NzU3MjkS1mt=1rt=0 Alternatively, to recommend a subscription to your library, please visit http://links.ealert.nature.com/ctt?kn=46m=34883478r=Mzg0ODUxNzc3MQS2b=2j=NzM2NzU3MjkS1mt=1rt=0
交流促进奥林匹克运动发展 Exchange Promote the Evolution of Olympics An isolated population without gene flow will gradually decline. A country locks its doors against the world will finally fall. In the same light, an olympic sport without exchange will lose its charm. In the Beijing 2008 Olympic Games, let me show you many examples as follows: A. Chinese coaching abroad: 1. Lang Ping, the head coach of the US women's volleyball team, led the US team climbed out of the doldrums and returned to the rank of the world's top volleyball teams. Now they beat the China team in the preliminary round and won the silver medal finally. 2. Li Mao became coach of the Korean men's badminton team in 1999. He trained Shon Seung Mo to win a silver medal at the Athens Olympic Games. After Athens, he worked for the Malaysian team and coached Li Chongwei, who also won a silver at the Beijing Olympic Games. 3 Qiao Liang, now head coach of the US women's gymnastics team, is the trainer behind famous US gymnast Shawn Johnson, who grasped one gold and three silvers at this year's Beijing Olympic Games. 4 Many more .... although they do cause a lot of trouble for Chinese players but more importantly, the make the sports more brilliant. B. Foreign coaches @ china: 1. Zhang Juanjuan, coached by a South Korean, won China's first- ever Olympic archery title by beating her South Korean competitors. 2. French coach Christian Bauer helped Zhong Man beat French Nicolas Lopez 15-9 to win the men's fencing gold medal. 3. Swimmer Zhang Lin, after a short private training session with Denis Cotterell, won China's first silver medal in men's swimming. 4. Japan's Masayo Imura helped Chinese synchronized swimmers win a first-ever bronze medal. 5. South Korean Kim Chang-back, the field hockey coaching guru for China. His team won a historic silver medal. 6. Spain's Juan Jane Giralt coached Chinese women's water polo team to a record fifth place. 7. Today China has foreign coaches in basketball, hockey, fencing, canoeing, tennis, judo, baseball and swimming. They are greatly helpful to the improvement of Chinses sports. Therefore, the sport communications with other countries will not make us weaker since the competition will keep one sport alive. The exchange will bloom both the development of olympic sports and the quality of human being. 没有基因流动的孤立种群会逐渐消亡; 闭关锁国的国家最终也会衰落; 同样地,没有交流的奥林匹克运动会丧失它的魅力。 北京2008奥运会,让我为你展示许多的例子: A 中国队的洋帅们: 1 击剑队法国外教鲍埃尔。不但为中国击剑带来了先进的训练历练和方法,还帮助仲满最终取得中国男子击剑的第一块奥运金牌。 2 花游队日本外教井村雅代。在她的努力下,中国选手最终在北京奥运会上实现了奖牌的突破。 3 女子曲棍球韩国外教金昶伯。在经过了三届奥运会的洗礼之后金昶伯和她的中国女曲终于在北京取得突破获得银牌。 4 射箭选手张娟娟在女子个人比赛中连克三名高手夺得金牌,为中国射箭项目实现了突破,打破了韩国在射箭项目的垄断地位,执教她的韩国教练杨昌勋堪称幕后的英雄。 5 中国在女子四人双桨项目上实现了赛艇金牌零的突破,虽然赛艇队主教练是中国人,但是立陶宛籍教练伊戈尔依然被水上中心主任韦迪称为功不可没。 6 在皮划艇项目中,中国选手孟关良/杨文军成功卫冕,波兰裔的加拿大人马克无疑是他们夺金背后最大的功臣 7 此外在夺得一金的中国跆拳道队,也有美籍韩裔教练李大成和韩国籍教练金荣稹的努力和汗水。 8 收获两金的中国拳击队的哈萨克斯坦籍教练努尔哈里和摔跤队的德国外教尼斯基也做出了奉献。 9 张琳在男子400米自由泳中获得了一枚含金量堪比冠军的银牌,为中国男子游泳选手实现了奥运奖牌的突破。曾经执教过澳大利亚名将哈克特的丹尼斯教练帮助张琳创造了这个历史。 10 更多的外国教练们,感谢他们促进了中国体育的发展。 B 海外的中国教练 1. 美国女排主教练郎平让美国女排重新焕发出了新的活力,也让她们继1984年奥运会后再次闯进奥运会女排的决赛。 2 在本届北京奥运会上,新加坡女队出现在决赛中与中国女团进行了冠军争夺,她们最终获得银牌,这是新加坡取得的第一枚奥运奖牌。而他们的主教练是刘国栋。 3 澳大利亚跳水队总教练童辉。北京奥运会上,澳大利亚夺得男子单人10米台金牌和女子双人10米台银牌,堪称继中国队之后的第二大赢家。 4 美国体操女队主教练乔良。远赴美国发展并发现了肖恩-约翰逊这个体操小天才,肖恩在这次北京奥运会上更是独得一金三银。 5 韩国羽毛球男单主教练李矛先后担任中国、韩国、马来西亚羽毛球队教练,并培养出董炯、孙俊、朴成焕、李铉一、孙升模等一大批赫赫有名的羽毛球世界名将。 6 更多的海外中国教练,虽然他们给我们的优势项目制造了麻烦,但也使我们的比赛更加精彩。 因此,同其他国家进行体育交流不会使我们更弱因为竞争可以使某个运动项目更有生机。交流不但可以繁盛奥林匹克运动,也会提升人类自身的素质。 资料参考 References: 1 中国辉煌勿忘洋帅功劳 郎平乔良们亦赢得世界掌声. http://nf2008.oeeee.com/a/20080825/631591.html 2 Chinese coaching abroad? Just think globally. http://www.chinadaily.net/olympics/2008-08/17/content_6943918.htm 3 Cheer for Lang Ping. http://www.chinadaily.com.cn/olympics/2008-08/20/content_6953749.htm 4 Coaches without borders. http://www.china.org.cn/olympics/team_china/2008-08/15/content_16231345.htm 5 Foreign coaches in China. http://www.nbcolympics.com/destinationbeijing/news/newsid=162207.html 6. Coaches try to play the game. http://www.chinadaily.com.cn/cndy/2008-08/24/content_6965204.htm