伪多项式时间

✍ dations ◷ 2025-11-29 17:35:35 #理论计算机科学,计算复杂性理论,复杂度类,算法分析

在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值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}})$ 。因此，上述算法是一个伪多项式时间算法。

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

相关

结石结石指人或其他动物在体内器官空腔或导管腔中形成的块状固体物。常见的结石有肾结石、胆结石、肝结石、输尿管结石、膀胱结石、结膜结石、唾液线结石等。结石的常见成分为钙
嫡妻嫡妻，或称正室、正妻、正房，俗称大老婆、大婆，是一夫多妻的家庭里面礼制上与丈夫平等的妻子。东亚古代男子一般同时只能有一位正妻，称为嫡妻；宋代之前，古中国只有贾充等数人因特殊
1771年兹姆里·利姆授职仪式壁画，从前1775年到前1760年创作。现在巴黎卢浮宫博物馆。
福寿螺主扭舌非正式群组 Architaenioglossa福寿螺（学名：Pomacea canaliculata），是一个大型的淡水螺物种，有鳃和口盖，是一种淡水生的苹果螺科腹足纲软体动物。苹果螺科旧属中腹足目，今属新
诺曼征服英格兰诺曼人征服（Norman conquest）或诺曼人征服英格兰（法语：Conquête normande de l'Angleterre）指1066年法国诺曼底公爵威廉对英格兰的入侵及征服。这次征服改变了英格兰的走向，从此
失职行为失职行为（malpractice、渎职行为；不端行为；不正当行为；专业人员失职行为；公务员职权滥用罪）在侵权行为法中亦称专业过失（英语：Professional negligence in English law），即是"专业上的
下丘脑-垂体-肾上腺轴下视丘-垂体-肾上腺轴 (HPA或HTPA轴)，也被叫做边缘系统-下视丘-垂体-肾上腺轴（LHPA轴），是一个直接作用和反馈互动的复杂集合，包括下视丘（脑内的一个中空漏斗状区域）,脑垂体（下视丘
维克多·格林尼亚弗朗索瓦·奥古斯特·维克多·格林尼亚（法语：François Auguste Victor Grignard，1871年5月6日－1935年12月13日），法国化学家，诺贝尔化学奖得主。他于1871年5月6日出生于法国瑟堡，193
三氟乙酸亚铜三氟乙酸亚铜是一价铜的三氟乙酸盐，化学式为CF3COOCu。三氟乙酸亚铜可由氧化亚铜和三氟乙酸酐在干燥的苯中于60-70℃反应，得到苯加合物。将苯加合物在真空中加热至110-120℃升
高登·摩尔高登·厄尔·摩尔（英语：Gordon Earle Moore，1929年1月3日－），英特尔公司的共同创办人之一。他最为人知的事迹，是提出摩尔定律。截至2015年1月，他的净资产为67亿美元。在2019年美国400