期末的眼泪都是当年选专业脑得来的水… 联合形式方法专业委员会：出版“不确定多项式时间”术语

期末的眼泪都是当年选专业脑得来的水…

Best Value Schools曾经发表了【最简单】【最秃顶】大学的专业调查。

今天我们一起看看你的专业有没有上榜。

虽然P.S .排行榜不具备一定的科学性，但是不能考虑每个人的能力和兴趣，所以只要自己热爱，就是最好的专家。

据说是最简单的专家

英语文学

English Literature关于英语文学专业，最难的部分是需要阅读。

除此之外，就不怎么动脑筋了。

很多情况下，学生要做的是读文学作品，讨论文学作品，自己写文学作品……内容比较简单，但相应地在就业方面没有多少选择。

很多学生选择成为作家和老师，也有做研究宣传和市场营销的人。

创造性的文章

对于喜欢写作的人来说，Creative Writing是必修课。

和英语文学专业的同学很相似。 他们花在创造性写作上的时间大部分是写作和学习其他作品。

最终的职业选择仅限于作家和市场营销。

人类学

虽然Anthropology人类学研究不足以成立公司，也不需要相关证书，但学习人类学的人大多都是出于对自己专业的热爱和兴趣，让他们更好地了解世界和自己的专业人士。

说实话，这个专业真的找工作不太好。 大部分就业的毕业生从事商业和广告业，少数当老师去教人类学。 当然，这是基于你获得人类学硕士和博士学位。

语言专业

学习语言其实是一项相当简单的任务。 这完全是关于记忆的，是依赖人脑的学科，所以记忆优秀的人们会变得轻松。

试着改变想法。 如果你在有专家的教育下，学四年同一门语言，这还不简单吗？

但是，根据所学的语言，俄语等专业很难。 该专业毕业生可以从事翻译、广告、编辑、外国公务员等工作。

教育

Education的研究表明，进入该专业的学生平均SAT得分最低，实习项目等工作与孩子在一起。

这足以证明它比其他专业容易。

各行各业都需要优秀的老师，但对于高学历教育学专业的毕业生来说，他们通常很容易找到工作，但从已知的中美教师平均工资来看，并不高。

公关和公关

Communications PR在这两个领域都需要当众讲话，有时还需要写大量的文章，因此有些人很难。

幸运的是，这个领域没有繁杂的脑力劳动和数学研究。

职业前景也比较广阔，许多毕业生在市场营销和业务管理方面取得了进步。

据说是最秃顶的职业选手

工程技术

大学平均辍学率： 8.3%的工程专业所有学生，无论选择什么方向，都要学习所有工程领域的基础知识。 这是因为工程师希望能够快速学习和理解更多的信息，以便能够进入指定的领域。

工科学生每周平均课时为19小时，这是所有其他大学专业中最高的。

此外，大多数课程还要求学生参加实验室。 也就是说，学生不仅要上课，还要有更多的时间坐在实验室里。

再加一个，课和实验室都有作业。

但是工程师的初始工资非常大，根据美国大学和雇主协会的数据，工程师的平均初始工资是61，872美元。

物理科学物理科学

大学平均辍学率： 6.9%这个专业很难。 因为成绩对毕业来说很重要。

学生有每周测试、实验室测试，还有典型的期中考试和期末考试，学生的GPA大部分取决于在这些测试中的成绩。

和工程学位一样，化学、天文学、物理、数学等工程除了课程和学校作业外，还需要实验室工作，比如在实验室写大量书面论文和进行额外的测试。

报酬不及工学毕业生，平均起薪为$ 44，000。

生物科学Biological Sciences

大学平均辍学率： 6.7%的人对生物学专业的学生抱有很大的期望。 因为他们可能会学到有用的东西，之后也有稳定的工作。

但是生物科学确实是个难学的专业，课程难就意味着教授很严格，这个专业很难通过。

生物科学学位的人平均工资约为32，000美元，远远比不上医学院的学生。

商科商务

大学平均辍学率： 7.2%对，还有商科！ 这里说的商科是指商学院的会计和财务专业。

因为这些专业是高度基于数学的，所以对讨厌数学的人来说可能是很难的专业。

需要很多学习时间，因为要进行很多测试，所以很多学生发现很难维持高的GPA。

辛苦的工作也得到了回报，工资约为55，600美元。

物流专业工资最高，管理、网络系统和会计次之。

建筑结构

大学平均辍学率： 7.2%获得建筑师学位需要巨大的野心.同样有很多测试和作业，需要大量的手写，需要优秀的批判性思维，这都是“秃顶”的部分。

建筑师的工资约为33，000美元，但项目经理可以赚更多。

经济学Economics

平均6.5%的大学辍学率的经济学科要求学生具有良好的数学技能和快速轻松地适应新事物的能力。 我们的世界和经济学的世界在不断变化，这意味着学生可以做到这一点。

经济学专业的工资是$43,000。

上述排行榜中有你的心仪专家吗？

学校季节到了，报名的同学得抓紧时间！

当然，申请的第一关是语言成绩！

在雅思、托福、GRE、GMAT

遇到有困难的同学

快来找我们，只有惊讶没有失望

联合形式方法专业委员会：出版“不确定多项式时间”术语

此次发布用语新词：非确定性多项式时间( Nondeterministic Polynomial Time )。

非确定多项式时间

(非详细轮询时间)

作者：李国强(上海交通大学)。

开头指南这次增加了非确定多项式时间( Nondeterministic Polynomial Time )这个新术语。 先锋网

非确定性多项式时间是一个复杂性问题，属于复杂性理论。

InfoBox :中文名称：非确定多项式时间

英文名： Nondeterministic Polynomial Time

缩写： NP

学科：计算复杂性理论的基本概述：又称NP问题，是一类非确定性图灵机在多项式时间内可以解决的判定问题。

也可以定义为可以通过确定性图灵机在多项式时间内验证答案是否正确的问题。

从定义上可以看出，确定性多项式时间问题(也称为p问题)属于非确定性多项式时间问题。 也就是说，p是NP的子集。

p和NP的两个集合相等吗？=NP问题(的结论尚不清楚，是数学、计算机科学领域的一大难题。

一些不确定性多项式时间问题中还有一类问题彼此等价，共同刻画了不确定性多项式时间问题中最难的一类问题。

这些是非确定性多项式时间完备问题( NP-complete，也称为NPC问题)。

所有的NP问题都可以在多项式时间内规定为任意的NPC问题。

在p和NPC都没有一个NP问题的情况下，我们称为非确定性多项式中间问题( NP-intermediate，也称为NPI问题)。

拉德纳证明了如果p不等于NP，则NPI集合不是空的[1]。

研究人员一直试图在同样复杂性的假设下证明整数分解问题等自然计算问题是NPI。

发展历程： 1936年，图灵建立了理论计算模型——图灵机[2]。

随着计算机在20世纪40年代和50年代的发展，图灵机被证明是正确的计算理论模型。

研究人员很快发现，基本图灵机无法解释计算机所需的时间和内存大小，但时间和空间在早期计算时代尤为重要。 20世纪60年代，哈特曼和斯特恩提出以输入长度为参数测量时间和空间长度函数，计算复杂度应运而生[3]。

随着研究者将高效计算定义为输入大小的多项式长，引出了非确定性多项式时间的完备性和NP问题。

20世纪70年代初期，库克和卡普的工作表明，许多组合和逻辑问题都是NPC问题[4-8]。

从那以后直到现在，这个问题已经成为计算机科学领域和数学领域的突出开放性问题。

后来兴起的电路复杂性、量子计算等理论领域，也为我们更好地理解p提供了很大的帮助吗？=NP问题这一计算机科学的宝物。

典型的例子：因为p问题是NP问题，所以所有具有多项式时间算法的问题都是NP问题。

图论上的最短路径问题、最小生成树问题、强连通部件问题、欧拉图问题等。

其他图论问题是NPC问题。

旅行商问题、哈密顿问题、独立集问题、顶点覆盖问题、群问题、图着色问题等。

数论问题中，素数判定问题于2004年由3位印度学者提出的AKS算法得到了素数测试的多项式算法[9]，该结论也获得了2006年的哥德尔奖。

另一个有名的问题是整数分解问题，作为现代密码学的基础没有多项式时间的算法，但研究者认为其判定问题版本(等价于原问题)不是NPC问题。

随着量子计算的兴起，绍尔获得了大数分解的多项式时间量子算法，动摇了现代密码学的基础[10]。

但是，那个不能解决p吗？=NP问题。

在代数问题中，线性规划中有多项式时间的算法，而整数规划是NPC的。

作为整数规划子问题，0-1方程式、子集和问题也是NPC的，另外一些问题本质上也是代数问题，例如区分问题、背包问题等，它们也是NPC的。

这些问题都是NP问题。

卡普最先收集总结了21个NPC问题[11]。 此后，许多学者热衷于总结NPC问题，经典算法书中对此部分进行了详细阐述。

最后要注意的是，在NPC问题中，如满足性问题(也称为SAT问题)那样，实际上并不一定存在高效的算法，作为NPC的第一个问题(4)，称为DPLL算法( 12，13 )的高效算法是不存在的

同时，存在高效的工具满足性问题求解器。

现在，形式化验证[ 14，15 ]、软件工程[16]、甚至深度学习[17]的许多工具通过将各个问题约定为可满足性问题求解器来实现效率化。

参考文献

1.r.ladner.onthestructureofpolynomialtimereducibility.journaloftheacm.vol.22 (1) 155171，1975。

2.Alan turing.oncomputablenumbers.in proc.ofthelondonmathematicalsociety，1936。

3.hartmanisandr.Stearns.onthecomputationalcomplexityofalgorithms.transactionsoftheamericanmathematicalsociety，vol.vol

4.s.cook.thecomplexityoftheorem-proving procedures.in proc.of3rdacmsymp.theoryofcomputing，151，158，1971。

5.s.cook.ahierarchyfornondeterministictimecomplexity.journalofcomputerandsystemsciences，vol.7(4)，343-353，

6.s.cook.anoverviewofcomputationalcomplexity.communicationsoftheacm，vol.26(6):400-408，1983。

7.r.Karp.reducibilityamongcombinatorialproblems.incomplexityofcomputercomputations，85-104. Plenum Press，New York

8. R. Karp. Combinatorics，complexityandrandomness.communicationsoftheacm，vol.29(2)，98-109，1986。

9. M. Agrawal、N. Kayal、andn.sa xena.primesisinp.annalsofmathematicsvol.160 (2)、781-793和2004。

10.p.w.shor.algorithmsforquantumcomputation:discretelogarithmsandfactoring.in proc.of35 thannualsymposiumonfoundattion

11.r.m.karpreducibilityamongcombinatorialproblems.complexityofcomputercomputation，85103，1972。

12. Davis，Martin； Putnam，Hilary.acomputingprocedureforquantificationtheory.journaloftheacm，vol.7(3)，201215，1960。

13. Davis，Martin； Logemann，George； Loveland，Donald.amachineprogramfortheoremproving.communicationsoftheacm，vol.5(7) 394397，1961。

14. A. Biere，A. Cimatti，E. M. Clarke，Andy.Zhu.symbolicmodelcheckingwithoutbdds.in proc.of the5thinternationationationationalationals

15. E. M. Clarke，A. Gupta，o.ST richman.sat-basedcounterexample-guidedabstractionrefinement，ietransactionsonconconcon

16. J. Dolby，m，Vaziri，f.tip.findingbugsefficientlywithasatsolver，in proc.of the6 thjointmeetingoftheeeeuropeansoftwansoftwsolver

17. G. Katz、C. Barrett、D. L. Dill、K. Julian、m.j.kochenderfer.relu plex:anefficientsmtsolverververifyingdex

作者简介

上海交通大学李国强副教授li.g@sjtu.edu.cn的主要研究方向是形式化验证、程序语言理论、知识推理与验证术语工业委员会和术语平台介绍：计算机术语检定委员会( Committee on Terminology )的主要功能是

这对明确学科体系，开展科学研究，在全社会广泛传播科学和知识具有十分重要的意义。

术语平台CCFpedia的建设和不断优化，既能有效推进我国计算机术语的收集、检定、规范和传播，又能起到各个领域规范化标准定制的推动作用。

新版本的CCFpedia计算机术语平台http://term.ccf.org.cn )集成了术语的编辑运行和浏览使用，消除了旧版本跨平台操作的繁琐步骤，大大升级了接口

此外，新版平台通过引入知识图谱对所有术语数据进行了组织，并以图像多层关联的形式对术语浏览的应用形态进行了升级。

计算机术语检定工作委员会主任：刘挺(哈尔滨工业大学)副主任：王昊勇(同济大学)李国良)清华大学)主任助理：李一斌(上海海乂知信息科技有限公司)丁军)上海海乂知信息科技有限公司)林俊宇)中国科学院信息工程研究所)兰艳艳