PSPACE-hard
时间: 2023-08-31 19:11:52 浏览: 59
PSPACE-hard问题是指那些可以在多项式空间内解决的问题,且所有PSPACE中的问题都可以在多项式时间内归约到这些问题。如果一个问题是PSPACE-hard问题,并且它本身也属于PSPACE,那么这个问题就是PSPACE-complete问题。PSPACE-complete问题被认为是PSPACE中最难的问题,因为解决了PSPACE-complete问题就等于解决了所有PSPACE中的问题。\[3\]
#### 引用[.reference_title]
- *1* *2* [P,NP,PSPACE都是什么,一文讲清计算复杂性分类](https://blog.csdn.net/2301_77724032/article/details/130365685)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
- *3* [GO is Polynominal-Space Hard](https://blog.csdn.net/qq_21335763/article/details/45331679)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]