伪多项式时间

✍ dations ◷ 2024-09-20 12:41:30 #理论计算机科学,计算复杂性理论,复杂度类,算法分析

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

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

相关

阿基米德浮体原理阿基米德浮体原理（或直接称为阿基米德原理或浮力原理）是阿基米德发现的原理。该原理是说，浸在流体中的物体（全部或部分）受到竖直向上的浮力，其大小等于物体所排开流体的重力。其公
百米公引，又称粨（英式英文：hectometre、美式英文：hectometer，记号hm）是国际单位制之一，为“百”和“米”的合字，即100米；此单位现已较少使用，曾较常用于度量道路、桥梁、铁路。米（m） · 尧米
磨床磨床（Grinding machine）是一种利用磨具研磨工件之多余量，以获得所需之形状、尺寸及精密加工面的机床。磨床的加工动作即为研磨，研磨工作在机械加工中居于首要地位，切削刀具的磨锐
光纤分布式数据接口光纤分布式数据接口（英文：Fiber Distributed Data Interface，FDDI）是美国国家标准学会制定的在光缆上发送数字信号的一组协议。虽然FDDI逻辑上是基于令牌环架构，但不是以IEEE 802
多莉·麦迪逊多莉·佩恩·托德·麦迪逊（Dolley Payne Todd Madison，1768年5月20日－1849年7月12日）是詹姆斯·麦迪逊的妻子，其丈夫在1809年至1817年担任美国总统一职。他以社交送礼闻名，增强了
彼得·戴蒙德彼得·阿瑟·戴蒙德（英语：Peter Arthur Diamond，1940年4月29日－），美国犹太裔经济学家、麻省理工学院教授，以对最优税收理论的研究而知名。2010年，他与戴尔·莫滕森、克里斯托弗·皮
沙格港不明飞行物事件沙格港不明飞行物事件（英语：Shag Harbour UFO incident）是发生在1967年10月加拿大新斯科舍省沙格港（Shag Harbour, Nova Scotia）的一起有档案记录的大型不明物体撞击事件。加拿大
林方一林方一（1883年12月6日－1932年12月10日），生于日本山口县佐波郡柚野村，台湾日本时期商人，台南林百货创办者。林方一出身贫苦农村，其母在他四岁时过世，其父林泷吉在他七岁时过世，依靠
鲁斯基乌斯·拉努维努斯鲁斯基乌斯·拉努维努斯公元前2世纪初期的罗马共和国拉丁喜剧作家，也是泰伦斯的评论家。曾创作大量拉丁喜剧等作品，名扬一时。现均已失传。
安东尼·范·迪门安东尼·范·迪门（荷兰语：Antonio van Diemen），1593年出生于荷兰屈伦博赫，1645年4月19日逝世于巴达维亚。为任期自1636年至1645年间的荷属东印度总督，是巩固荷兰在远东殖民力量的