5 The hierarchy of cpmplexity classes
language: 字符串的集合。
predicates: means
捶牢。也就是說(shuō)，predicates也可以看成一個(gè)字符串得集合。
定義： complement of languages co-
設(shè)是一個(gè)language得集合掠河，則對(duì)偶集合co-
由所有
中l(wèi)anguage的補(bǔ)組成。正是來(lái)說(shuō)猛计，
由定義出發(fā)唠摹， 我們馬上可以得到 P=co-P, BPP=co-BPP, PSPACE=co-PSPACE。
5.1 Games machines play
考慮兩個(gè)人W和B玩的游戲奉瘤。首先有一個(gè)字符串W和B都可以看到勾拉，之后WB輪流給出字符串，例如
盗温，且這些字符串的長(zhǎng)度是
的多項(xiàng)式藕赞。W和B可以看到對(duì)手之前已經(jīng)給出的字符串。
從這個(gè)游戲的輸贏出發(fā)定義復(fù)雜度類(lèi)型卖局，考慮的是time complexity.
Theorem 
5.2 The class PSPACE
Theorem(PSPACE的game語(yǔ)言的定義)
存在多項(xiàng)式游戲斧蜕，滿(mǎn)足
{
: 當(dāng)輸入為
時(shí)，W有贏的策略 }砚偶。
下面是各個(gè)計(jì)算復(fù)雜度種類(lèi)的包含關(guān)系
計(jì)算類(lèi)別的包含關(guān)系
