伪多项式时间

✍ dations ◷ 2025-12-06 12:53:09 #理论计算机科学,计算复杂性理论,复杂度类,算法分析

在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。

一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为强NP完全问题。

在素性测试中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数N，使用从最小的素数2开始，到 ${\sqrt {N}}$ $\sqrt{N}$ 为止的整数依次对N进行试除，如果均无法整除N，则N是素数，这个过程需要进行至多约 ${\sqrt {N}}$ $\sqrt{N}$ 次整数除法，即其时间复杂度为 $O({\sqrt {N}})$ $O({\sqrt {N}})$ ，为N的多项式。令D为N的二进制表示的位数，那么N可以表示为以2为底D的幂，因此素性测试问题的时间复杂度用D表示应为 $O(2^{D/2})$ $O(2^{{D/2}})$ 。因此，上述算法是一个伪多项式时间算法。

其它被证明只具有伪多项式时间算法解的问题有背包问题，子集合加总问题。

相关

张京育张京育（1937年4月27日－），生于湖南湘潭，中华民国政治人物、教育家，中国国民党籍，曾任政治大学校长，中华民国行政院大陆委员会主任委员、总统府国策顾问。获国立政治大学学士、硕士学
钩骨钩骨（Hamate）或钩状骨（unciform bone）是人类手腕上的骨头，其主体成楔形，且有一钩状骨突，向掌面突出。钩骨为手腕中一块形状不规则的腕骨，位于较远端一排的腕骨，且紧靠着小指和无名指
巴黎大区系统竞争力集群法国“巴黎大区系统竞争力集群”（法语：SYSTEM@TIC PARIS-REGION）成立于2005年，致力于复杂系统的研究工作。现有大型企业分支机构100个，中小企业210家，研究实验室80所，出资支持的地
性感的残酷《性感的残酷》（英语：The Sexy Brutale）是一款由骑士游戏工作室以及龙舌兰工作室（英语：Tequila Works）共同开发的冒险解谜游戏。游戏已经于2017年4月发行于PlayStation 4、Microso
卡尔·斯图姆夫卡尔·斯图姆夫（Carl Stumpf，1848年4月21日－1936年12月25日）是一位德国哲学家和心理学家。卡尔·斯图姆夫出生在德国巴伐利亚维森泰德，师从弗朗兹·布伦塔诺和鲁道夫·赫尔曼·陆
YouTube总部枪击案太平洋时间2018年4月3日12时46分，美国加利福尼亚州圣布鲁诺的YouTube总部附近发生了一起枪击案。伊朗籍的女性嫌犯持枪攻击位于加州圣布鲁诺的YouTube总部，之后自杀身亡，造成至
第10太阳周期第10太阳周期是从1755年开始纪录太阳黑子以来的第10个太阳周期，这个周期开始于1855年12月，结束于1867年3月，持续了11.3年。最大平滑黑子数(超过12个月期间的黑子月平均数值)为9
Another角色列表本列表列出了日本小说《Another》及其衍生动画、电影中的角色。榊原恒一（榊原恒一（さかきばらこういち），声优：阿部敦（日语）、格雷格·艾尔斯（英语））榊原家的儿子，15岁。因为父亲工作
马耳他总理马耳他总理（Prime Minister of Malta） (马耳他语：Prim Ministru ta' Malta)是马耳他的政府首脑。由马耳他议会选举产生。1921年马耳他自治政府成立，其首脑称为首席部长(Head of
力学概念评量力学概念评量（Force Concept Inventory）简称FCI，是在物理学习一学期后，评量学生程度的工具，由David Hestenes（英语：Hestenes）、Halloun、Wells及Swackhamer提出（1985年）。是第一个这类