姜咏江 为了理解好P与NP问题,特作图解释。 1. P 、 NP 、 NP-complete 和 NP-hard 之间的关系图 下面 Fig.1 是国外网站见到的 P 、 NP 、 NP-complete 和 NP-hard 之间的关系图。因为没有归约表示,因而较难理解。 Fig. 1 Diagram for P, NP, NP-complete and NP-hard in case P ≠ NP. Fig.2 是我整理的 P 、 NP 、 NP-complete 和 NP-hard 之间的关系图。图中用带箭头虚线表示归约关系,是否能够更好地理解? Fig. 2 虚线表示规约方向 从 Fig.2 科研看出,所有的 NP 问题(其中包括 P 问题)都可以通过多项式时间算法(程序过程)转化成 NP-complete 问题,转化的结果仍然是 NP 问题。 如果所有的 NP 问题都能转化为 NP 之外的问题,这些问题就是 NP-hard 问题。注意,整个平面都不是问题,因而应该认为除去这几种关注的问题之外,还有问题存在。 2. 为什么说 P=NP-complete 就有 NP=P ? 从 Fig.2 不难看出,当 P=NP-complete 时, NP 内的两个椭圆就合成了一个,即有所有的 NP 问题都可以在多项式时间内归约为 P 问题,也就有了“所有 NP 问题都可以在多项式时间内求出解”的结论。如此一来,当然 NP=P 了。 3. NP-hard A problem A is NP-hard when every problem Lin NP can be reduced in polynomial time to A. 这是说,所有 NP 都能够在多项式时间归约到一个不属于 NP 的问题,这个问题就是 NP-hard. 由 Fig.2 你容易看到,如果 NP-hard=P 就 可以说明 P=NP 。
图解头痛现象 诸平 头痛(headache) 是临床常见的症状,近九成人有头痛症状。通常将局限于头颅上半部,包括眉弓、耳轮上缘和枕外隆突连线以上部位的疼痛统称头痛。头痛病因繁多,神经痛、颅内感染、颅内占位病变、脑血管疾病、颅外头面部疾病、以及全身疾病如急性感染、中毒等均可导致头痛。发病年龄常见于青年、中年和老年。 临床上根据 头痛 起病方式将头痛分为: ①急性起病的头痛:常见如 蛛网膜下腔出血 和其它脑血管疾病、 脑膜炎 或 脑炎 等; ②亚急性起病的头痛:如 颞动脉炎 、 颅内肿瘤 等; ③慢性起病的头痛:如 偏头痛 、紧张型头痛、 丛集性头痛 、 药物依赖 性头痛等。 根据 头痛 发生病因,国际头痛协会于2004年制定的第二版“头痛疾患的国际分类”(the International Classification of Headache Disorders 2nd Edition, ICHD-II)将头痛分为三大类: ①原发性头痛(the primary headaches):包括 偏头痛 、紧张型头痛、 丛集性头痛 等; ②继发性头痛(the secondary headaches):包括头颈部外伤、颅颈部血管性因素、颅内非血管性疾病、感染、药物戒断、精神性因素等多种原因所致的头痛; ③颅神经痛、中枢性和原发性面痛、以及其它其他颜面部结构病变所致头痛及其他类型头痛。 虽然引起 头痛 的病因很多,但是,头痛大致可分为原发性和继发性两类。前者不能归因于某一确切病因,也可称为特发性头痛,常见的如 偏头痛 、紧张型头痛;后者病因可涉及各种颅内病变如脑血管疾病、颅内感染、颅 脑外伤 ,全身性疾病如发热、内环境紊乱以及滥用精神活性药物等。 《今日医学》 ( Medical Daily )网站,2015年7月2日采用图解方式,对于疼痛现象进行了介绍,特摘引如下,供大家参考。 Here's everything you need to know about headaches. Visual.ly Headaches are very common — like 90 percent of the population common. Just because headaches are common, though, that doesn’t mean you should be caught off guard when your next painful bout hits. So, here’s everything you need to know about every kind of headache, including tension-type headache, migraine headache, sinus headache, chronic daily headache, and the dreaded cluster headache . Ninety percent of the population experiences a headache at some point in their lifetime, however, certain people have to deal with headaches or migraines that are a lot more severe than others. Half of the global population has suffered a severe headache at some point, 25 percent suffer from recurring severe headaches, 12 percent have migraine headaches, and four percent have chronic daily headaches. Although there are both over-the-counter and prescription medications designed to treat specific types of headaches, there are also easy at-home remedies that can help alleviate the throbbing pain that just won’t quit. The next time you’re struggling with a headache, try: relaxing and resting, an ice pack, moderate exercise, dietary supplements, hydration, pressure points/gentle massage, taking a hot shower, or diet; multiple small meals.
. School of Computing University of Utah 大学的 Matt Might 先生有个颇有意思的简短博文, The illustrated guide to a Ph.D, 姑且译为 图解何为博士 。于是就把它转帖过来、并大意翻译一下,供大家欣赏一下。 . 原文 参考 及其链接:http://matt.might.net/articles/phd-school-in-pictures -------------------------------------------------------------------------------------------------------------- 1. Imagine a circle that contains all of human knowledge ( 设想人类所有的知识为上面的一个圆。注:也就是说,圆内为人类所已知,圆外为人类所未知 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2. By the time you finish elementary school, you know a little ( 当你读完小学时,你就有所了解一小点 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3. By the time you finish high school, you know a bit more ( 当你读完中学时,你的知识又略微增多了一点 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 4. With a bachelor's degree, you gain a specialty ( 当你拿到学士学位时,你的知识又增加了一些,并且还多了个专业方向 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 5. A master's degree deepens that specialty ( 硕士阶段的学习会让你的专业知识更加纵深发展 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 6. Reading research papers takes you to the edge of human knowledg ( 阅读研究论文最终让你接触到专业知识的最前沿 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 7. Once you're at the boundary, you focus ( 一旦接触到专业前沿,你就会集中力量钻研某一点 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 8. You push at the boundary for a few years ( 连续数年,你都会全身心致力于此点 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 9. Until one day, the boundary gives way ( 直到一天,终于有所突破 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 10. And, that dent you've made is called a Ph.D ( 正因为那一专业点的突破,你才能被称之为博士 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 11. Of course, the world looks different to you now ( 当然,此时你的世界也就焕然一新 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 12. So, don't forget the bigger picture ( 但不要忘记还有那个更大的人类知识之圆圈 ) 13. Keep pushing . ( 所以,要继续奋力向前推进 )。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -------------------------------------------------------------------------------------------------------------- .