伪多项式时间

✍ dations ◷ 2025-12-01 12:40:09 #理论计算机科学,计算复杂性理论,复杂度类,算法分析

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

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

相关

定律定律，或称科学定律（英语：Scientific law或Laws of science）、科学法则，为研究宇宙间不变的事实规律所归纳出的结论，不同于理论、假设、定义、定理，是对客观事实的一种表达形式，通过
热容热容量（英语：heat capacity）是一定量的物质在一定条件下温度升高1度所需吸收的热量，用符号C 表示，单位是J·K-1或J·℃-1。其公式为：C = lim
面心立方堆积立方晶系，也叫等轴晶系，它有4个三重对称轴以及3个互相垂直的4次对称轴或者3个相互垂直的二重对称轴。其中的3个互相垂直的4次对称轴或者3个相互垂直的二重对称轴是晶体结晶轴
农艺学农学，狭义上专指农艺学（英语：Agronomy）是研究与农作物生产相关领域的科学，包括作物生长发育规律及其与外界环境条件的关系、病虫害防治、土壤与营养、种植制度、遗传育种等领域。
衙役衙门差役（简称衙差、衙役），古代中国吏役名。衙门内实际主管侦缉逮捕、处理管辖地区行政及司法事务的职位或人员。衙门差役于位阶上，与衙门胥吏相同的，都属于没有官品的行政人员，甚
永全片湘语永全片，分布在湘桂走廊一带，东起湖南省衡阳市祁东县附近，向西延伸到广西壮族自治区的兴安县和灌阳县。该片使用人口达600余万。永全片包括全州话、永州话、祁阳话等，最大的
原台北酒厂华山1914文化创意产业园区（又名华山1914文创园区或华山1914，英语：Huashan 1914 Creative Park），园区前身为“台北酒厂”，为台湾台北市市定古迹。在1999年后，成为提供给艺文界、非营
中华人民共和国教育部直属高等学校列表截至2015年8月，中华人民共和国教育部直属高等学校共有75所。说明：根据中央教育科学研究所高等教育研究中心2009年12月发布的《中国高等学校绩效评价报告》，在教育部直属72所高
蜂群崩溃综合征蜂群崩溃综合征（英语：Colony Collapse Disorder，缩写：CCD），或称蜂群衰竭失调，大批蜂巢内的工蜂突然消失，欧洲蜜蜂蜂群大量死亡，造成蜜蜂生态崩解。于2006年末在美国首次将这个现象命
二次离子质谱二次离子质谱（英语：Secondary Ion Mass Spectroscopy, SIMS）是用来分析固体表面或者是薄膜的化学成分的技术，其用一束聚焦的离子束溅射待测品表面，并通过检测轰击出的二次离子的