2008-08-01 17:27:57| 分类： computer science | 标签： |举报 |字号大中小 订阅

http://en.wikipedia.org/wiki/PSPACE-complete#Examples_of_PSPACE-complete_problems

Mathematicians and computer scientists try to carefully define different types of complexity, and **PSPACE-complete** is one of these types. Roughly, PSPACE is all the problems which can be solved by programs which only need a polynomial (in the length of the problem instance specification) amount of memory to run, and it turns out that some of these problems are essentially as hard as any such problem can be. Such problems are called **PSPACE-complete**.

## Contents[hide] |

In complexity theory, a decision problem is **PSPACE-complete** if it is in PSPACE and every problem in PSPACE can be reduced to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE. These problems are widely suspected to be outside of P and NP, but that is not known. It is known that they lie outside of NC.

The first known NP-complete problem was the Boolean satisfiability problem (SAT). This is the problem of whether there are assignments of truth values to variables that make a boolean expression true. For example, one instance of SAT would be the question of whether the following is true:

The SAT problem can be generalized to the quantified Boolean formula problem (QBF), an important PSPACE-complete problem that allows both universal and existential quantification over the values of the variables:

- .

The proof of that QBF is a PSPACE-complete problem is essentially a restatement of the proof of Savitch's theorem in the language of logic, and is a bit more technical.

Notice that the NP-complete problem resembles a typical puzzle: is there some way to plug in values that solves the problem? The PSPACE-complete problem resembles a game: is there *some* move I can make, such that for *all* moves my opponent might make, there will then be *some* move I can make to win? The question alternates existential and universal quantifiers. Not surprisingly, many puzzles turn out to be NP-complete, and many games turn out to be PSPACE-complete.

Examples of games that are PSPACE-complete (when generalized so that they can be played on an *n* × *n* board) are the games hex and Reversi and the solitaire games Rush Hour, Mahjong, Atomix, and Sokoban. Some other generalized games, such as chess, checkers (draughts), and Go are EXPTIME-complete because a game between two perfect players can be very long, so they are unlikely to be in PSPACE.

Note that the definition of PSPACE-completeness is based on *asymptotic* complexity: the time it takes to solve a problem of size *n*, in the limit as *n* grows without bound. That means a game like checkers (which is played on an 8 × 8 board) could never be PSPACE-complete (in fact, they can be solved in constant time and space using a very large lookup table). That is why all the games were modified by playing them on an *n* × *n* board instead; in some cases, such as for Chess, these extensions are somewhat artificial and subjective.

Another PSPACE-complete problem is the problem of deciding whether a given string is a member of the language defined by a given context-sensitive grammar.

Following are a few PSPACE-complete problems with outlines of the algorithms showing that they are in PSPACE. More examples can be found at list of PSPACE-complete problems.

- Let TQBF = { <F> : F is a true fully quantified boolean formula }. On input F:
- If F has no quantifier, evaluate and accept iff F is true.
- If F=pF', recursively evaluate F'[p=1] and F'[p=0], accept iff both accept.
- If F=qF', recursively evaluate F'[q=1], F'[q=0] and accept iff at least one accept.

- Space Usage: The number of levels of recursion is equal to the number of variables of F. The amount of information stored at each level of recursion is constant (values of formula for p=0 and p=1). Therefore the total space used is linear.
^{[1]}

See Game complexity for more games whose completeness for PSPACE or other complexity classes has been determined.

- On input <G,b>:
- If b has no outgoing edge, reject.
- Otherwise, remove b and all its edges, call this new graph G
_{1}. - Recursively run on inputs <G
_{1},b_{i}>, where each b_{i}are the endpoints of edges from b. - Reject if all accept; otherwise accept.

- Space Usage: The number of levels of recursion is equal to the number of nodes in G. The amount of information stored at each level of recursion is equal to the number of nodes in G. Therefore the total space used is linear.
^{[2]}

- Michael Sipser (1997).
*Introduction to the Theory of Computation*. PWS Publishing. ISBN 0-534-94728-X. Section 8.3: PSPACE-completeness, pp.283–294. - Michael R. Garey and David S. Johnson (1979).
*Computers and Intractability: A Guide to the Theory of NP-Completeness*. W.H. Freeman. ISBN 0-7167-1045-5. Section 7.4: Polynomial Space Completeness, pp.170–177.

**^**François Pitt. "Lecture Summary for Week 11 work" (html). Retrieved on 2008-02-12.**^**François Pitt. "Lecture Summary for Week 11 work" (html). Retrieved on 2008-02-12.

评论这张

<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->

## 评论