伪多项式时间

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

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

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

相关

211工程211工程（英语：Project 211），俗称“211院校”，是指1990年代起，中华人民共和国政府针对中国高等教育发展所策划、实行的一项战略性政策。“211”的含义是“面向21世纪、重点建设100
海豹突击队美国海军三栖特种部队（英语：United States Navy SEa, Air and Land Teams，SEAL），一般称作海豹突击队，是直属美国海军的一支特种部队，亦是世界知名的特种三栖部队，主要任务包括：非常规
公立常青藤公立常春藤（英语：Public Ivies）是指一些可以提供常春藤盟校教育体验，但只需公立学校价格的公立大学。《The Journal of Blacks in Higher Education》杂志将她们比作是“成功地
铈的同位素铈（原子量：140.116(1)）的同位素，其中有1个同位素是稳定的，另外有3个目前归类为稳定的同位素，理论上都会进行双β衰变（衰变为钡或钕），但是半衰期都只有下界。备注：画上#号的数据代表没
顶点 (曲线)在描述曲线时，顶点是指该曲线上曲率相对于附近其他点的极值，更正式地，在几何学中会将曲线中曲率的一阶导数为零的点称为曲线上的顶点:570:126，而这个点通常会是曲线中的区域极值
预防原则预防原则（德语：Vorsorgeprinzip）指凡有活动或政策对公众或环境有不可回复的损害威胁时，不得以缺乏充分的科学证据为由，推迟符合成本效益的预防措施。旨在防止环境恶化，而非回复或
召唤兽召唤兽是因为任何原因而被召唤至任何地点的非人类生物的总称。虽然名为召唤兽，但不一定是兽类的动物，除了实际存在的生物以外，也包括幻想生物。
印度流浪儿问题据估计，如今印度大约有40万无家可归的儿童存在。他们主要是因为家庭冲突而流落街头，住在街上，自行照顾自己及工作谋生。虽然流落街头的儿童会联合起来以保护自己，他们往往会被雇
贾马鲁尔·基拉姆三世贾马鲁尔·基拉姆三世（1938年7月16日－2013年10月20日)20日清晨病逝于菲律宾马尼拉的一家医院中，他曾经掌领菲律宾苏禄苏丹国，被称为“世上最贫穷的苏丹 ”。他参加了2007年菲律
第14太阳周期第14太阳周期是从1755年开始纪录太阳黑子以来的第14个太阳周期，这个周期开始于1902年2月，结束于1913年8月，持续了11.5年。最大平滑黑子数(超过12个月期间的黑子月平均数值)为64