多项式时间

✍ dations ◷ 2025-04-26 12:55:12 #计算复杂性理论,计算资源

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

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

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

相关

西征欧洲长子西征，又称蒙古第二次西征、蒙古侵略欧洲（英语：Mongol invasion of Europe），是蒙古帝国继成吉思汗西征花剌子模后的第二次大规模的西征。1235年开始至约1242年，历时约8年，因由各
迈克尔·法拉第迈克尔·法拉第（英语：Michael Faraday，1791年9月22日－1867年8月25日），英国物理学家，在电磁学及电化学领域做出许多重要贡献，其中主要的贡献为电磁感应、抗磁性、电解。虽然法拉第没
按揭抵押（mortgage），是指提供私人资产（不论是否为不动产）作为债务担保的动作，多发生于购买房地产时银行借出的抵押贷款或在典当商折现非不动产的物品。抵押常在银行或地产界使用。在广
多歧苏铁多歧苏铁（学名：）是属于苏铁科的一种植物，是苏铁属的一种。属于常绿小乔木，分布于中国云南、广西及越南，模式产地为云南建水县，海拔1100米邻近红河之地区。花期4至5月，果期10至11月。
生日攻击生日攻击是一种密码学攻击手段，所利用的是概率论中生日问题的数学原理。这种攻击手段可用于滥用两个或多个集团之间的通信。此攻击依赖于在随机攻击中的高碰撞概率和固定置换
埃庇米尼得斯埃庇米尼得斯（Epimenides）古希腊克里特岛人，预言家、诗人，传说他在宙斯的神圣洞穴中沉睡57年，不过在醒来之后获得预言的能力。他创造过一个克里特悖论，他说：“所有克里特人都说谎。
格里莫二世格里莫二世（法语：Grimaud，？－714年），又名小格里摩尔德，加洛林家族成员，法兰克王国纽斯特里亚宫相（695年－714年）。法兰克王国宫相赫斯塔的丕平与正妻普雷科特鲁德（英语：Plectrude）所生的次子
台湾山荠台湾山荠（学名：），又名台湾葶苈，是十字花科山荠属的一种多年生草本植物，分布于台湾海拔3000－3900米的山区，为台湾特有种植物。本种最早于1934年由日本植物学家大井次三郎（英语：Jisaburo
词源《词源》是宋朝词人张炎于其晚年编写的词论专著，词法承传自沈义父《乐府指迷》，分有上下二卷，上卷详论词乐韵律，下卷历论作词要法。张炎于下卷阐明成书缘由，主要是不满南宋灭亡后
杨达 (1935年)杨达（1935年－），男，祖籍广东开平，中国粤语相声演员，一级演员。杨达祖籍广东省开平市塘口镇四九村。1957年起加入广东民间音乐团（现广东音乐曲艺团）表演广东民歌，1958年起与黄俊英合作表