基于概率圖靈機(jī)模型的復(fù)雜性類.pdf

1、該文主要基于概率圖靈機(jī),研究隨機(jī)復(fù)雜性類和交互式證明系統(tǒng)中的一些有趣的問題.概率工具在復(fù)雜性的研究中不儀是一個(gè)很有用的工具,同時(shí)也提出了新的研究課題.所謂概率圖靈機(jī),它除了正常的輸入以外,還具有投擲硬幣的能力;最終的輸出和輸入及擲硬幣得到的隨機(jī)串都有關(guān).在這樣的模型下,理論科學(xué)家們定義了一些相應(yīng)的語言類—BPP,ZPP,RP,PP.交互式證明系統(tǒng)有兩個(gè)很重要的特點(diǎn)—交互性和隨機(jī)性.驗(yàn)證方的計(jì)算能力是多項(xiàng)式的概率圖靈機(jī).證明方的能力不限,

2、提供相應(yīng)的證據(jù)給驗(yàn)證方.對(duì)于不同的輸入,證明方能夠以不同的概率去說服驗(yàn)證方;根據(jù)驗(yàn)證方被說服的概率,我們可以區(qū)分開一個(gè)語言和它的補(bǔ)集,從而交互式證明系統(tǒng)接受了這個(gè)語言該文首先介紹了復(fù)雜性研究中常用的模型和基本概念,對(duì)概率圖靈機(jī)和交互式證明系統(tǒng)做了基本的介紹.第二部分基于概率圖靈機(jī),給出了RP的定義和NP的另外一種定義;然后介紹ZPP和PP的等價(jià)定義;最后,詳細(xì)討論了兩個(gè)介于BPP和PP之間的語言類.第三部分對(duì)圖不同構(gòu)問題進(jìn)行研究,提出了