PSPACE

✍ dations ◷ 2025-10-12 13:30:14 #复杂度类,计算机科学中未解决的问题

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。

相关

  • 流体流体(英语:Fluid)就是在承受剪应力时将会发生连续变形的物体,包括气体和液体。流体没有一定形状,几乎可以任意改变形态,或者分裂。具有黏性的流体在发生变形时将产生阻力,而没有黏
  • 花萼花萼是一朵花中所有萼片的总称,位于花的最外层,一般是绿色,样子类似小叶,但也有少数花的花萼样子类似花瓣,有颜色。花萼在花还是芽时包围着花,有保护花瓣作用,花开放后花萼托在最外
  • 飞行速度飞行速度记录是特定种类飞行器所能达到的最高速度。所有官方航空记录都由国际航空联合会(FAI)定义并正式通过。飞行记录被分为若干个级别和副分类。飞行器被分为三个种类:陆基
  • 舱外活动:2000年之后本列表包含了所有的2000年至2014年之间的太空行走;即所有宇航员完全或部分离开航天器的事件。舱外活动开始及结束时间均为协调世界时(UTC)时区。
  • Csub10/subHsub8/subNa萘钠是一种有机盐,化学式为NaC10H8/ C10H8Na,离子化学式为Na+C10H8−。在实验室研究中,它被用作有机化学、有机金属化学和无机化学合成中的还原剂。尚未制得固体,一般是现配现用
  • 戴王缙戴王缙(?-?),字绅黄,号云极,直隶沧州(今河北)人,清朝政治人物,进士出身。顺治十五年(1658年)登戊戌科进士,官行人司行人。著有《萧云斋集》。高祖戴才,明万历间尚书。父戴明说,清顺治间尚书。
  • 本田中心本田中心(英语:Honda Center)是一座位于美国加州的橘郡安那翰市中心的室内体育馆,由日本本田技研工业冠名赞助。
  • 里夫战争Manuel Fernández Silvestre† Dámaso Berenguer José Millán Astray (负伤(英语:Wounded in action)) Miguel Primo de Rivera Alfredo Kindelán José Sanjurjo Leopoldo
  • 段展段展(越南语:Đoàn Triển/.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS-UNI-H","Ming-
  • 理查德·阿文·奥弗顿第二次世界大战理查德·阿文·奥弗顿(英语:Richard Arvin Overton,1906年5月11日-2018年12月27日),美国超级人瑞,享嵩寿112岁230天,逝世之前亦是最年老的二战美国老兵以及最年老的美