伪多项式时间

✍ dations ◷ 2025-12-05 23:38:26 #理论计算机科学,计算复杂性理论,复杂度类,算法分析

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

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

相关

菲利普·肖瓦特·亨奇菲利普·肖瓦特·亨奇（英语：Philip Showalter Hench，1896年2月28日－1965年3月30日），美国医生，1920年获得匹兹堡大学医学博士。由于发现肾上腺皮质激素及其结构和生理效应，他与爱德华
武功歌武功歌（法语：Chanson de geste）是在法语文学开端出现的史诗。已知最早的武功歌出现在11世纪晚期和12世纪早期，是在游吟诗人的抒情诗和最早的骑士诗之前。
菲涅耳衍射在光学里，菲涅耳衍射（Fresnel diffraction）指的是光波在近场区域的衍射。菲涅耳衍射积分式可以用来计算光波在近场区域的传播，因法国物理学者奥古斯丁·菲涅耳而命名，是基尔霍夫
陶一世塞纳赫特里·雅赫摩斯是古埃及第二中间期，第十七王朝的第七位法老。塞纳赫特里在希克索斯第十五王朝统治下埃及时，统治了上埃及底比斯区域。他至少于公元前1560或1558年驾崩。
蛙鞋蛙鞋，是潜水装备（英语：Diving equipment）的一种，亦用于其他水类运动，包括：游泳、身体冲浪（英语：Bodysurfing）、跪板冲浪（英语：Kneeboarding (surfsport)）、水底曲棍球、水底榄球（英语：水底
清朝文学清朝文学多元发展，兼容并包历代之文学特色。明朝以前的文学发展多表现在声韵、格律、句法、结构的因袭或创变；清朝承接各代文学成果，先后形成许多学派，将各种在明朝以前已式微的
明正天皇明正天皇（1624年1月9日－1696年12月4日，在位期间：1629年12月22日－1643年11月14日），为后水尾天皇第二皇女，母亲中宫德川和子。讳兴子，幼名女一宫。元和九年十一月初十日（1623年12月4日），兴
千层饼千层饼，是一种多层酥饼，通常每层饼之间会夹有甜味陷料。千层饼有多种变种，如拿破仑饼、香草薄饼、巧克力薄饼、奶油薄饼、蛋奶薄饼等。它经典的味道是奶黄味，有时也有泡打奶油和
农校篝火农校篝火（Aggie Bonfire)是德州农工大学的一项长久存在的校园传统，同时也是该校与德克萨斯大学奥斯汀分校的大学竞争的一部分。九十年来，德州农工学生，也称Aggies，每年秋季都在校
知识贬值知识贬值是指知识所带来的经济价值随时间而不断减低的现象。虽然这种现象早在20世纪初就已出现，但最先把这种现象作具体描述的，应该是日本前经济企划厅厅长堺屋太一。根据堺屋