P (复杂度)

✍ dations ◷ 2025-04-05 00:25:06 #复杂度类,最优化

在计算复杂度理论中,P(polynomial time class)是在复杂度类问题中可于确定型图灵机以多项式量级(或称多项式时间)求解的决定性问题。

P通常表示那类可以“有效率地解决”或“温驯”的可计算型问题,就算指数级非常高也可以算作“温驯”,例如RP与BPP问题。当然P类别存在很多现实处理上一点也不温驯的问题,例如一些至少需要n1000000指令来解决的问题。很多情况下存在着更难的复杂度问题

P包含了很多已知的自然问题,例如决定性版本的线性规划,计算最大公因数,以及发现最大匹配。在2002年,判别一个数是否为质数也被人解出是一个P问题。与功能性问题(function problem)相关的类别是FP。

P的扩大集合是NP,此复杂度类是一个可在多项式时间以非确定型图灵机决定答案的问题的集合。因此我们可知道P是NP的子集,且虽然未证明,但大部分专家相信P是NP的严格子集(即NP一定大于且包含P集合)。

P也已知至少大于L一个可在对数量级的存储器空间上决定的问题的类别。一个判定算法使用了O(log )的空间就不可能使用超过2O(log )=O(1)的时间,因为这是所有可能组合方式的总数,因此L是P的子集合。另一个重要问题是:L是否相等于P?我们已知P=AL(问题可在对数存储器上以另类图灵机(alternating Turing machine)解决的问题之集合),而P也已知不大于PSPACE(可在多项式空间判定的问题)。再一次,我们面对P是否等于PSPACE的未知问题。整理一下上述问题:

EXPTIME指的是可在指数时间解答的问题类别。在上列的类别关系中,只有两个严格包含关系是确定的:

在P问题中最困难的是P完备问题。

另一个P的扩大集合是P/poly,或非统一多项式时间。若一个问题落于P\poly,则它可以在依据输入内容的长度下给予提示字符串(advice string)的情况下,以确定性多项式时间解决。然而,不像NP,此多项式时间机器不需要侦测伪造提示字符串;因为它不是一个验证机器。P/poly是一个几乎包含所有实际算法的巨大类别,包含所有BPP。如果P/poly包含了NP,则整个多项式层次结构将会下降到第二层次结构。另一方面,它也包含一些不切实际的算法,包含一些可决定问题,例如一元版的任何非决定性问题。

多项式时间算法拥有组装封闭性。换句话说,若我写了一个内容是多项式时间的函数(若视函数调用为固定时间),且其它被本函数调用的副函数也属于多项式时间,则整个组合起来的算法也会是多项式时间。因此P是自我低陷的,这也是P被认为是无关机器类型的主要理由:任何机器特征(例如随机存取)可以用多项式时间算法模仿的话,可在一些更简单的机器以其他多项式时间算法组合并化约而成,且时间复杂度依然是P。

Kozen指出Cobham与Edmonds是最可信,最早创造多项式时间这个名词的人。

相关

  • 德国鸢尾德国鸢尾(学名:Iris germanica)是鸢尾科鸢尾属的植物。分布于欧洲以及中国大陆的青岛、江苏、湖北等地,目前已由人工引种栽培。植株无性繁殖系群体花花花
  • 纳吉布拉穆罕默德·纳吉布拉·阿赫马德扎伊(普什图语:ډاکټر نجیب ﷲ احمدزۍ‎,英语:Mohammed Najibullah Ahmadzai,1947年8月6日-1996年9月28日),阿富汗政治家、共产主义者,出生
  • 绿色农业绿色农业为一种21世纪后兴起的新农业模式,发展复合农林业、减少土地开垦、使用天然肥料等新型绿色农业技术,复合农林业是一种旨在单位土地上获得最大效益的土地利用技术和经营
  • 热效率在热力学中,热效率( η t h {\displaystyle \eta _{
  • 缠斗缠斗(又名:空中格斗)是描述两架军用飞机在近距离战斗的型态,大多数的场合是描述两架或者多架战斗飞机企图击落或者威胁对方的空中战斗作为。缠斗的英文原文为Dogfight,有直接翻译
  • 凯拉·米勒行动联合特种作战司令部 (JSOC)16至21人死亡巴里沙突袭(英语:Barisha raid),正式行动代号为凯拉·米勒行动(以美国人道主义工作者凯拉·米勒的名字命名), 是美国于2019年10月26至27日在
  • 马丁·奥马利马丁·约瑟夫·奥马利(英语:Martin Joseph O'Malley;1963年1月18日-),是一位美国民主党政治人物,曾任第61任(英语:List of Governors of Maryland)马里兰州州长(英语:Governor of Maryla
  • 金芝河金芝河(韩语:김지하,1941年2月4日-)本名金英一(김영일),出生于日治朝鲜全罗南道木浦市大安洞,毕业于首尔大学,为大韩民国诗人、思想家、社会活动家。芝河一名由来系发音与韩国语“地下
  • 红爪雨林蝎斯氏异蝎(学名:),又称为巨人雨林蝎、红爪雨林蝎,为目前纪录中已知体长最长的蝎子也是世界上最大的蝎子之一,可达23 cm(9.1英寸),体重则可达56克(2.0盎司)。红爪雨林蝎所具有的毒液一般
  • 南非兀鹫南非兀鹫(学名)是南部非洲特有的一种兀鹫,分布于南非、莱索托、博茨瓦纳及纳米比亚北部一些地区。它们会在崖边筑巢,一般每年会生一只蛋。南非兀鹫的身体呈深褐色,翼底则较为淡色