多项式时间

✍ dations ◷ 2025-12-04 14:09:37 #计算复杂性理论,计算资源

多项式时间（英语：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的缩写）。

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

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

相关

回补反应回补反应（英语：Anaplerotic reactions，也称补给反应或添补反应）是指形成代谢途径中间产物的反应。这样的例子可以是三羧酸循环。在该循环为呼吸作用而行使正常作用时，三羧酸循环
分子晶体分子晶体指的是物质内部由范德华力（又称作范德瓦耳斯力或分子间作用力）将分子结合起来的固体物质。晶体的内部由分子构成，大多数非金属单质（少数如Si等除外）、它们的化合物以及大
保靖县保靖县位于中国湖南省西部、是湘西州下辖的一个县。国内生产总值97,380万元（2004年），人口为286,612人（2003年），主要民族为土家族、苗族和汉族，其中土家族156,133人，苗族62,399人。保
新世纪资通新世纪资通股份有限公司（简称NCIC），是台湾民营电信固网公司之一，是由台湾远东集团及新加坡电信、统一企业等企业投资成立之固网公司，2001年2月14日取得固网执照并于同年开台营运
2007年亚足联亚洲杯2007年亚足联亚洲杯是第 14 届亚足联亚洲杯，于2007年7月7日至7月29日在东南亚四国印尼、马来西亚、泰国及越南举行，本届赛事是历史上首次由四个国家共同主办的国际体育赛事。
3-乙基戊烷3-乙基戊烷（英语：3-Ethylpentane）有时候也称为三乙基甲烷（英语：Triethylmethane）是一种支链烷烃，化学式CH(CH2CH3)3，是庚烷的同分异构体之一，主链为5个碳原子，支链为2个碳原子。3-乙基
汤姆·寇特内汤姆·寇特内（英语：Tom Courtenay，1937年2月25日－），英格兰男演员。他曾以《化妆师（英语：The Dresser）》(1983)获得金球奖最佳戏剧类电影男主角，并获得奥斯卡最佳男主角奖提名；他并以《
提姆·哈福德提姆·哈福德（英语：Tim Harford, 1973年－）是一位英国记者。生于1973年，1998年在牛津大学获得经济学研究型硕士学位。他是金融时报每周一期的专栏"Dear Economist"的撰稿人。Dear
Windows MeWindows Me（Windows Millennium Edition，版本号：4.9，开发代号：Millennium）是一个16位／32位混合的Windows系统，于2000年9月14日由微软公司发行。Windows Me是现时最后一个基于DOS的混
千里金兰大学千里金兰大学（日语：千里金蘭大学）是一所位于日本大阪府吹田市的私立女子大学，始建于1905年的私立金兰女学校，2003年正式设置为四年制大学。金兰出自中国古籍易经中“二人同心，其利