伪多项式时间

✍ dations ◷ 2025-12-02 10:57: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}})$ 。因此，上述算法是一个伪多项式时间算法。

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

相关

海洋科学海洋学（英语：oceanography）是研究海洋的自然现象、性质及其变化规律，以及开发利用海洋的知识体系。它是研究海洋的地理学的分支。它涵盖了广泛的主题，包括生态系统动力学、洋流、
国际排名此表列出之数据是关于中华民国（台湾）在各国际指数中的名次，分母为该指数计算的国家总数：† if ranked以中华台北名义参赛
蓝松鸦冠蓝鸦（英文：blue jay 学名：Cyanocitta cristata），又名蓝松鸦、蓝㭴鸟，是雀形目鸦科冠蓝鸦属的鸟类，原产于北美洲，主要分布于美国落基山脉以东、圣皮埃尔和密克隆群岛和加拿大南部，属
美国伊斯兰教伊斯兰教是美国第三大宗教，仅次于基督教和犹太教。2017年的一项研究估计，有345万穆斯林生活在美国，约占美国总人口的1.1%.。此外，50％的穆斯林是在本土出生和成长，而另外50％是外国出
匈牙利国防军匈牙利国防军（匈牙利语：Magyar Honvédség），为匈牙利的武装力量，包含匈牙利陆军、以及匈牙利空军。现役10万人（2012年），预备役2.5万。匈牙利实行义务兵役制，士兵服役期为9个月。“国
AnimediaAnimedia（日文名：アニメディア），日本学习研究社所发行的动画杂志月刊。每月10日发售。自称“观看、阅读、装饰、参加有4倍乐趣的动画资讯杂志（見る・読む・飾る・参加する 4倍楽
樊弘樊弘（1900年7月15日－1988年4月18日），号止平，四川江津人，中国经济学家。樊弘于1925年毕业于北京大学政治学系。此后历任北平《国民公报》编辑、《中央晚报》编辑、北平社会调查所编
斯赫里贡达斯赫里贡达（Shrigonda），是印度马哈拉施特拉邦Ahmadnagar县的一个城镇。总人口26331（2001年）。该地2001年总人口26331人，其中男性13619人，女性12712人；0—6岁人口3248人，其中男1719人，
林鼎林鼎（891年－944年），字涣文。福建侯官(今福州市)人，生于明州（今浙江宁波）。林鼎曾仕吴越武肃王钱镠，为观察押牙，后进入文穆王钱元瓘幕府。后唐长兴三年（932年）钱元瓘继位后，林鼎署镇海军
皮内尔湖皮内尔湖（英语：Lake Peigneur，本地发音：.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Ge