伪多项式时间

✍ dations ◷ 2025-04-03 11:43:06 #理论计算机科学,计算复杂性理论,复杂度类,算法分析

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

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

相关

假根假根是植物和真菌的一种结构，和根一样用做支撑或吸收等用途。在真菌里，假根是由固定真菌的匍匐枝向下长的小小分歧菌丝。假根会释放出消化酶并吸收消化后的有机物质。在陆生植
超低频波长： 10000km 至 1000km超低频（英语：Super Low Frequency，SLF）指的是频率介于30Hz（赫兹）与300Hz间的电磁波。一般由变电所配送到居家的交流电频率多在此范围内，即50Hz～60Hz间。在无
III型分泌系统III型分泌系统（英语：Type III secretion system 缩写TTSS或T3SS）是革兰氏阴性菌的一个由多组分蛋白复合体形成的跨膜通道，它通过分泌蛋白，或把这些毒力蛋白直接注入宿主细胞中发
玛萨拉酒玛萨拉酒（英语：Marsala wine，意大利语：vino Marsala）是意大利西西里岛玛莎拉出产的葡萄酒。玛萨拉酒于1969年获得了法定产区葡萄酒（DOC）认证。尽管玛莎拉本地人有时喝原产的“葡萄
BT63基因改造水稻事件BT63基因改造水稻事件是一起中华人民共和国基因改造事件，事件跨度多年，影响范围逐渐遍及全球。水稻的起源在华中农业大学，原先在实验室经过基改后的样品在委外试植中，因为管控不
新安县新安县在中国河南省西北部、黄河南岸，是洛阳市下辖的一个县；位于黄河南岸，处河南、山西二省交界处，坐标为北纬34°36′-35°05′，东经111°53′-112°19′之间；境南与宜阳县接壤，西
日本昏迷指数日本昏迷指数（日语：ジャパン‧コーマ‧スケール，英语：Japan Coma Scale，简称为JCS），是指日本常用的意识障碍程度（或称意识程度）分类法。JCS依清醒程度分为三阶段，其中再细分为三阶段，因
克萨诺斯克萨诺斯(Xexanoth)是美国小说家霍华德·菲利普·洛夫克拉夫特所创造的克苏鲁神话中的一个邪恶存在。克萨诺斯最早出现在克拉克·A·史密斯(Clark Ashton Smith)的短篇小说
东柱：时代诗情《东柱：时代诗情》（韩语：동주）是由韩国大钟奖最佳导演李濬益执导，一部描写日治时期韩国独立运动诗人尹东柱（姜河那饰）的黑白传记电影，于2016年2月17日上映。导演李濬益也因为执导本
内容过滤路由器内容过滤路由器(Content filtering router)是一种特别的路由器，主要是让家长或学校对互联网连接内容的监控，藉以保护家中或学校的儿童免受色情、毒品、暴力、赌博以及仇视的内