注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Fly to the Sky!

很多人因为寂寞而错爱一个人,更多人因为错爱一个人而寂寞一生。

 
 
 

日志

 
 

[转]PSPACE-complete  

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

  下载LOFTER 我的照片书  |

From Wikipedia, the free encyclopedia

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]

[edit] Technical Description

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.

[edit] Examples of PSPACE-complete problems

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.

[edit] TQBF

  • 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]

[edit] Winning Strategies For Games

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

[edit] Generalized geography

  • On input <G,b>:
    • If b has no outgoing edge, reject.
    • Otherwise, remove b and all its edges, call this new graph G1.
    • Recursively run on inputs <G1,bi>, where each bi 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]

[edit] References

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

[edit] External links

  评论这张
 
阅读(1350)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

网易公司版权所有 ©1997-2017