PSPACE

✍ dations ◷ 2025-08-04 02:24:44 #复杂度类,计算机科学中未解决的问题

PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合,是Polynomial SPACE的简称。

如果规定 SPACE ( t ( n ) ) {\displaystyle {\mbox{SPACE}}(t(n))} 为PSPACE完全,如果它在PSPACE中,并且为PSPACE难,即

其中, A p B {\displaystyle {\mbox{A}}\leq _{p}{\mbox{B}}} 指的是存在从A到B的多项式时间归约。PSPACE完全问题对于研究PSPACE中的问题非常重要,因为它们代表了PSPACE中最困难的问题。如果一个PSPACE完全问题得到了时间上高效的算法,那么,对所有PSPACE中的问题都可以有时间上高效的算法,因为这些问题都能够被多项式时间归约到PSPACE完全问题。然而,这个性质对PSPACE难不成立,因为存在这样的问题,它们可能属于PSPACE难但不属于PSPACE完全,因为这些问题不属于PSPACE。

如果x属于P,则P = PSPACE - Hard,那这个x就可称为PSPACE - Hard。

围棋的复杂度已于1978年被Robertson与Munro证明为PSPACE-hard。

相关

  • 肌痛肌肉痛(英语:Myalgia),如字面意思所言——肌肉疼痛,是多种疾病的症状,其最常见的成因是肌肉(群)的过度拉伸、过度使用。没有肌肉创伤史的肌肉痛则通常是由病毒感染所引起,而长期肌肉
  • APP1AAP, 1AMB, 1AMC, 1AML, 1BA4, 1BA6, 1BJB, 1BJC, 1BRC, 1CA0, 1HZ3, 1IYT, 1MWP, 1OWT, 1QCM, 1QWP, 1QXC, 1QYT, 1TAW, 1TKN, 1UO7, 1UO8, 1UOA, 1UOI, 1X11, 1Z0Q, 1ZE7
  • 法理继承国家国家继承(英语:Succession of states)在国际法上,是指某一个国家因为一定的领土被别国取去,因而导致该国在国际上的部分或全部权利、义务、地位等,被取去其领土的国家所取代。取得
  • 任意子任意子(英语:anyon)是数学和物理学中的一个概念。它描述一类只在二维系统中出现的粒子。它是对费米子和玻色子概念的广义化。在石墨烯、量子霍尔效应等二维物理系统中任意子这
  • 联盟号联盟号运载火箭(又译为联盟号运载火箭,欧美简称A-2)是不可重复使用的发射系统,由Korler设计局制造研发,总部位在俄罗斯的萨马拉,曾经发射过载人的太空船,是一个从联合号出来的小分
  • 异针蚁亚科异针蚁亚科(Heteroponerinae)隶属于蚁科针蚁形态亚科群,下含1族3属,该亚科是 Barry Bolton 于2003从针蚁亚科分出的六亚科之一。
  • 军事占领军事占领(Military Occupation),亦称占领(Occupation),是指一国的领土的治权在战争中暂时转移到敌军(英语:Belligerent)的情形。军事占领是一种暂时的管理,无论持续多久都不能获得占领
  • 诺亚·埃莫里奇诺亚·埃莫里奇(英语:Noah Nicholas Emmerich,1965年2月27日-)是美国的一位演员,凭借电影美丽女孩而成名。他也出演过超级8,楚门的世界,玩命手机等电影和冷战谍梦等电视剧。他出生在
  • 真圆真円((1579年1648年-),俗名刘觉,江西省饶州府浮梁县人,明末清初时东渡日本僧人。1620年,搭乘商船在长崎上陆。1624年,出家为僧,是长崎地区最初的中国僧人。在同乡的华侨所创建的兴福寺
  • Jason-1Jason-1(英语:Joint Altimetry Satellite Oceanography Network - 1),亦称杰森一号,是由美国宇航局与法国空间局联合运营的一项地球观测与卫星测高任务,作为系列海面地形观测任务