P (复杂度)

✍ dations ◷ 2025-07-01 04:19:55 #复杂度类,最优化

在计算复杂度理论中,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是最可信,最早创造多项式时间这个名词的人。

相关

  • 心衰竭心脏衰竭(法语:Insuffisance cardiaque,英语:HF, heart failure),一般意指慢性心脏衰竭(英语:CHF, chronic heart failure)。但是有时则指郁血性心力衰竭(congestive heart failure),当
  • 第二型糖尿病2型糖尿病(英语:Diabetes mellitus type 2,简称T2DM,台湾称为第二型糖尿病),大陆旧称为非胰岛素依赖型糖尿病(英语:noninsulin-dependent diabetes mellitus,简称NIDDM)或成人发病型糖
  • span class=nowrapZr(SOsub4/sub)sub2/sub/span硫酸锆是一种无机化合物,化学式为Zr(SO4)2,它可以以无水物、四水合物、五水合物和七水合物的形式存在。它们是白色可溶于水的固体。硫酸锆可由二氧化锆和硫酸的反应得到:得到的
  • 色带色带,打印耗材,从最早的机械撞击式的打字机到后来的电脑针式打印机,使用的都是此物。色带的工作原理就是利用针式打印机机头内的点阵撞针或是英文打字机中的字母撞件,去撞击打印
  • 决号作战美利坚合众国英联邦陆军部队:美国太平洋陆军(总计52-54个师)海军部队:美国太平洋舰队空军部队:美国空军太平洋战略部队(英语:United States Strategic Air Forces in the Pacific)
  • 印花税法印花税法(英语:Stamp Act 1765)是英国议会对美洲英国殖民地所实行的税收法案。该法案要求所有美洲的出版物使用在伦敦生产且盖有印花的纸张并一同纳税。1763年,英国赢得英法北美
  • 雅浦州雅浦州是密克罗尼西亚联邦4个州之一,首府是科洛尼亚,辖有雅浦岛、萨塔瓦尔环礁,以及东面和南面延伸约800公里的14个珊瑚岛及环礁,包括欧里皮克环礁、埃拉托环礁、法斯岛、法劳莱
  • 锕衰变链锕衰变链是指锕-227的4n+3链。由少量存在于自然中的钚-239开始,该衰变链的衰变产物有铀、钍、镤、锕、钫、镭、氡、钋、砹、铋、铅、铊。它们都短暂或长期地存在于任何含有铀
  • 黄宗道黄宗道(1921年2月3日-2002年11月22日),原籍湖北孝感,出生于湖北武汉,中国天然橡胶及热作专家。1945年毕业于金陵大学农学院。1997年当选为中国工程院院士。
  • 核心大战《核心大战》(英语:Core War,又译作“磁芯大战”)是一款由D·G·琼斯和A·K·杜德尼在1984年创造的编程游戏,在游戏中两个或更多的战斗程序(称为“战士”)为了控制虚拟计算机而竞争