5 The hierarchy of cpmplexity classes
language: 字符串的集合。
predicates: means
。也就是说，predicates也可以看成一个字符串得集合。
定义： complement of languages co-
设是一个language得集合，则对偶集合co-
由所有
中language的补组成。正是来说，
由定义出发， 我们马上可以得到 P=co-P, BPP=co-BPP, PSPACE=co-PSPACE。
5.1 Games machines play
考虑两个人W和B玩的游戏。首先有一个字符串W和B都可以看到，之后WB轮流给出字符串，例如
，且这些字符串的长度是
的多项式。W和B可以看到对手之前已经给出的字符串。
从这个游戏的输赢出发定义复杂度类型，考虑的是time complexity.
Theorem 
5.2 The class PSPACE
Theorem(PSPACE的game语言的定义)
存在多项式游戏，满足
{
: 当输入为
时，W有赢的策略 }。
下面是各个计算复杂度种类的包含关系
计算类别的包含关系
网友评论