多项式时间

✍ dations ◷ 2025-12-08 21:29:05 #计算复杂性理论,计算资源

多项式时间（英语：Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间 $m(n)$ $m(n)$ 不大于问题大小 $n {\displaystyle n}$ $n$ 的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。

以数学描述的话，则可说 $m(n)=$ $m(n)=$ O $(n^{k})$ $(n^{k})$ ，此 $k {\displaystyle k}$ $k$ 为一常量值（依问题而定）。

数学家有时把“如多项式时间长的算法”视为快速计算，相对应的是超多项式时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。指数时间就是一例。

可以在决定型依序机器上（例如图灵机）以多项式时间解决的决定性问题，其属于的复杂度类被称为P。可以在多项式时间验证答案的决定性问题称为NP。而NP也是可以在非确定型图灵机以多项式时间解决的问题（NP两字为Non-deterministic Polynomial的缩写）。

多项式时间在决定型机器上是最小的复杂度类，且在机器模型改变时依旧强韧，且也是可在副程序组合过程中保持封闭的类别。

强多项式时间指的是此问题的运算时间不因输入资料的数字大小而变动，而是依照输入资料的结构复杂度（例如图论中的顶点数量）。

相关

风邪风邪是中医学上对一类外界环境致病因素的称呼，为六淫之一。《黄帝内经》中描述为：“风者，善行而数变。”。风邪为阳邪，侵袭部位多在表、在上，具有游走性，病情变化较多且较迅速。感
壮文壮文（壮语：Sawcuengh），又称拼音壮文，是一套使用拉丁字母来记录标准壮语的全音素文字，是壮语的官方书写系统。壮文于1955年创制，1982年修订。修订后的现行壮文又称“新壮文”。壮文
脱氧核糖核酸病毒脱氧核糖核酸病毒（英语：DNA virus），又称DNA病毒，其遗传物质为DNA。一般为正链DNA病毒。医学导航: 病毒病病毒(蛋白质)/分类cutn/syst (hppv/艾滋病, 流感/疱疹/人畜共患)/人名体
威南县威南县（马来语：Daerah Seberang Perai Selatan），是马来西亚槟城州在马来西亚半岛西岸南部的一个县。其面积为243平方公里，2010年人口为165,828。该县北以润绒河（Sungai Junjong）与
2019年伊斯坦布尔市长选举美鹿·乌伊萨尔（英语：Mevlüt Uysal）正义与发展党埃克雷姆·伊马姆奥卢（英语：Ekrem İmamoğlu）共和人民党2019年3月伊斯坦布尔市长选举连同2019年土耳其地方选举在3月31日举行
巴恩斯 (堪萨斯州)巴恩斯（英语：Barnes）是一个美国城市，位于堪萨斯州华盛顿县。根据2010年人口普查，城市人口为159人。巴恩斯位于39°42′41″N 96°52′23″W / 39.711525°N 96.873094°W / 39.71
川本芳昭川本芳昭（1950年－）是一名日本东洋史学者，目前担任九州大学名誉教授。出身于长崎县，1972年九州大学文学部东洋史学科毕业、1978年同大学院文学研究科博士课程单位取得退学。1981年
大渡口区文物保护单位重庆市大渡口区共公布一批文物保护单位，分别列表如下。
于贝尔·雷弗于贝尔·雷弗（法语：Hubert Reeves，1932年7月13日－），加拿大天体物理学家，科普推广者。出生于蒙特利尔，1953年从蒙特利尔大学科学系本科毕业，1955年从麦吉尔大学获得硕士学位，硕士论文是
御坊市御坊市（日语：御坊市／ごぼうし */?）是位于和歌山县中部临海的城市，为和歌山县纪日高地区的主要城市。辖区东侧为山区，西侧为位于日高川（日语：日高川）河口的日高平原，主要市区亦为于