P (复杂度)

✍ dations ◷ 2025-06-09 08:13:32 #复杂度类,最优化

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

相关

  • 鬼谷子鬼谷子(?-?),传说原名王诩,又作王禅、王利、王通,一说字诩,道号玄微子,世称鬼谷先生、王禅老祖,是大约活跃于战国中期的显赫人物,为“诸子百家”之一、纵横家的鼻祖,亦有政治家、外交家、
  • 线粒体核糖体线粒体核糖体是存在于真核细胞线粒体内的一种核糖体,负责完成线粒体这种细胞器中进行的翻译过程。线粒体核糖体的沉降系数介干55S-56S之间,是已发现的沉降系数最小的核糖体。
  • FeO(OH)铁锈为铁氧化物的统称,通常为红色,由铁和氧气境下进行氧化还原反应而生成。不同情况下会生成不同形式的铁锈。铁锈主要由三氧化二铁水合物Fe2O3·nH2O和氢氧化铁(FeO(OH), Fe(OH)3)
  • 田 波田波(1931年12月25日-2019年12月15日),男,山东桓台人。中国病毒学家。中国科学院院士。1931年12月生于山东省桓台县夏庄。高中时代先后就读于南京国立中央大学附属中学和青岛市立
  • 帽子帽子是戴在头部的服饰,有遮阳、挡雨、防尘、美观、保护头部等用途。以下列出几种常见的帽子款式,详见帽子款式列表.
  • font color=black共同外交与安全政策/font本文是 欧洲联盟的政治与政府 系列条目之一欧盟共同外交与安全政策(英语:Common Foreign and Security Policy,简称CFSP;法语:Politique étrangère et de sécurité commune,简
  • 义乌国际小商品博览会中国义乌国际小商品博览会,简称义博会,是每年10月21日至10月25日在浙江义乌的义乌国际博览中心举行的小商品博览会,创办于1995年。它是国务院批准的日用消费品类国际性展会,由商
  • 2019冠状病毒病美国疫情时间线2019冠状病毒病美国疫情时间线,介绍在2020年美国本土及领土内2019冠状病毒病疫情发生的情况。1月1月2月2月3月3月4月4月过去15日过去15日 1月21日1月24日1月25日1月26日1月29
  • 波罗的海国家理事会波罗的海国家理事会(英语:Council of the Baltic Sea States,缩写:CBSS)是由北欧波罗的海国家政府所组成的合作组织,于苏联解体后成立。理事会特别针对经济发展、能源、教育与文化
  • 疯狂店员2《疯狂店员2》(英语:)是一部于2006年上映的美国喜剧片,由凯文·史密斯执导、编剧和剪辑。本片为1994年电影《疯狂店员》的续集与View Askew宇宙的第六部电影;与第一集的黑白画面