伪多项式时间

✍ dations ◷ 2025-11-22 18:40:21 #理论计算机科学,计算复杂性理论,复杂度类,算法分析

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

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

相关

再献圣殿节灯台光明节灯台（希伯来语：.mw-parser-output .script-hebrew,.mw-parser-output .script-Hebr{font-size:1.15em;font-family:"Ezra SIL","Ezra SIL SR","Keter Aram Tsova","Taam
英式英语英国英语（British English，简写：BrE、BE、en-GB），又称英式英语，主要是指居住在不列颠群岛上的英格兰人的英语口音及规则，为英国本土及英联邦国家的官方语言。并非所有英国人认同英
露点‎大气物理学大气力学（英语：Synoptic scale meteorology）天气 (分类) · (主题)气候 (分类) 气候变迁 (分类)露点（英语：Dew point）或露点温度（英语：Dew point temperature）是在固定气
法律及司法培训中心法律及司法培训中心（葡文：Centro de Formação Jurídica e Judiciária，葡文缩写：CFJJ）是澳门特别行政区的政府部门，于2001年4月2日成立，由行政法务司监督，负责提供司法及法律领域
新西兰国际广播电台新西兰国际广播电台（英语：Radio New Zealand International，英语简称RNZI）是新西兰的官方广播电台，也是新西兰国家广播电台的对外广播部门，广播内容有新闻和体育节目，语言以英语为
戈德华特－尼科尔斯国防部重组法案戈德华特—尼科尔斯法案（英语：Goldwater–Nichols Act）1986年颁布，对美国军队的指挥系统进行了重新构架。该法案增强了参谋长联席会议主席的权力，并且采纳了罗纳德·里根总统于19
衡阳县衡阳县隶属于湖南省衡阳市。位于湖南省中部，衡阳市西北部，湘江中游，因位于南岳衡山之南而得名。东与南岳区、衡山县交界，南毗蒸湘区、石鼓区、衡南县，西邻祁东县、邵东市邵东县，北
超科超科（Superfamily），又译作总科，是生物分类法中的一个层级，介于亚目和科之间。有时在超科和亚目之间还有下目（或称次目）的分类。一般超科名称的拉丁字尾是-oidea。
汽车设计汽车设计（英语：Automotive design）是一门涉及汽车外观美术设计、工程学、以及人体工程学等范畴的专门行业。现在一般所称的汽车设计是指汽车在美学与功能方面的工业设计，而非车
发酵乳制品发酵乳制品是经过发酵的乳制品。通过发酵，牛奶中所含的一些乳糖被微生物分解为乳酸，并产生乙醛、丙酮、丁酮等香气物质。发酵增加了产品的保质期，同时提高了产品的口味并改善了