第11章計(jì)算復(fù)雜性理論簡(jiǎn)介11.1計(jì)算模型

11.2P類和NP類問(wèn)題

11.3NPC問(wèn)題將存在多項(xiàng)式時(shí)間算法的問(wèn)題看作是易解問(wèn)題，將需要指數(shù)時(shí)間級(jí)算法解決的問(wèn)題看作是難解問(wèn)題。11.1計(jì)算模型

11.1.1求解問(wèn)題的分類歸納起來(lái)，在各種求解問(wèn)題中，按求解問(wèn)題算法的時(shí)間復(fù)雜度可分為3大類：存在多項(xiàng)式算法的問(wèn)題肯定不存在多項(xiàng)式算法的問(wèn)題尚未找到多項(xiàng)式算法，也不能證明其不存在多項(xiàng)式算法的問(wèn)題。第三類問(wèn)題介于第一類和第二類之間。當(dāng)圖靈機(jī)的讀寫(xiě)頭掃描到一個(gè)格的字符時(shí)，根據(jù)控制器的當(dāng)前狀態(tài)和掃描到的字符，決定圖靈機(jī)的動(dòng)作，包括3方面：輸入帶a1a2…ai…anBB……讀寫(xiě)頭有限狀態(tài)控制器控制器進(jìn)行狀態(tài)轉(zhuǎn)換（決定下一狀態(tài)）讀寫(xiě)頭上當(dāng)前格寫(xiě)上新的字符決定讀寫(xiě)頭向左或向右移動(dòng)一格11.1.2圖靈機(jī)模型圖靈機(jī)模型的基本結(jié)構(gòu)：輸入帶a1a2…ai…anBB……讀寫(xiě)頭有限狀態(tài)控制器一條向右無(wú)限延伸的輸入帶（可讀可寫(xiě)）一個(gè)有限狀態(tài)控制器和連接控制器與輸入帶的讀寫(xiě)頭輸入帶由一個(gè)個(gè)格組成，每一格可以存放一個(gè)字符1.確定性圖靈機(jī)Q是有限狀態(tài)集，q0（q0∈Q）是初始狀態(tài)，F(xiàn)（F

Q）是終止?fàn)顟B(tài)集，Γ是輸入帶的符號(hào)集。B（B∈Γ）是空白符。∑是Γ中除B外的輸入字母表。δ：Q×?！鶴×?！羬L，R}是動(dòng)作函數(shù)，其中L表示左移一格，R表示右移一格，對(duì)于某些q∈Q和a∈Γ，δ(q，a)可以無(wú)定義。確定性圖靈機(jī)的定義如下：圖靈機(jī)是一個(gè)七元組M=(Q，∑，Γ，δ，q0，B，F(xiàn))。把輸入串a(chǎn)1a2…an（ai∈∑）放置在輸入帶上，如放置在最左端，開(kāi)始時(shí)讀寫(xiě)頭注視輸入帶上某一格，如注視最左端的第一格，M的初始狀態(tài)為q0。在每一步，讀寫(xiě)頭把掃描到的字符（設(shè)為xi）傳送到有限狀態(tài)控制器，有限狀態(tài)控制器根據(jù)當(dāng)前狀態(tài)q和動(dòng)作函數(shù)δ(q，xi)確定狀態(tài)的變化，在當(dāng)前格寫(xiě)上新字符以及移動(dòng)讀寫(xiě)頭。當(dāng)進(jìn)入某個(gè)終止?fàn)顟B(tài)或δ(q，xi)無(wú)定義時(shí)，圖靈機(jī)M停機(jī)。圖靈機(jī)M的工作過(guò)程：用符號(hào)→表示推導(dǎo)關(guān)系，其中*表示多步推導(dǎo)。設(shè)當(dāng)前瞬像為x1…xi-1qxi…xn，表示當(dāng)前狀態(tài)為q，讀寫(xiě)頭正注視著xi字符。

若δ(q，xi)=(p，y，L)，則i=1時(shí)不能進(jìn)行下一步推導(dǎo)（讀寫(xiě)頭無(wú)法向左移），當(dāng)i>1時(shí)有：

x1…xi-1qxi…xn→

x1…xi-2pxi-1yxi+1…xn即將xi改為y，讀寫(xiě)頭左移一格并注視xi-1字符，狀態(tài)變?yōu)閜。若δ(q，xi)=(p，y，R)，則有：

x1…xi-1qxi…xn→x1…xi-1ypxi+1…xn即將xi改為y，讀寫(xiě)頭右移一格并注視xi+1字符，狀態(tài)變?yōu)閜。對(duì)于圖靈機(jī)M，能夠從初始狀態(tài)出發(fā)，最終到達(dá)某個(gè)終止?fàn)顟B(tài)的輸入串為該圖靈機(jī)所接受的符號(hào)串。

所有這樣的符號(hào)串構(gòu)成的集合稱為該圖靈機(jī)所接受的語(yǔ)言。

【例1.11】設(shè)計(jì)一個(gè)圖靈機(jī)M，它接受的語(yǔ)言L={0n1n|n>1}，設(shè)計(jì)該圖靈機(jī)。

解：假設(shè)輸入串w為00…011…1BB…，設(shè)計(jì)出來(lái)的圖靈機(jī)的主要功能是檢查0的個(gè)數(shù)和1的個(gè)數(shù)是否相等。

使讀寫(xiě)頭往返移動(dòng)，每往返移動(dòng)一次，就成對(duì)地對(duì)輸入符號(hào)串w左端的一個(gè)0和右端的一個(gè)1做標(biāo)記。0011B…如果恰好把輸入串的全部符號(hào)都做了標(biāo)記，說(shuō)明左邊的符號(hào)0與右邊的符號(hào)1的個(gè)數(shù)相等，則w屬于L；否則，或者左邊的0已全部標(biāo)記，右邊還有若干個(gè)1沒(méi)有標(biāo)記，或者右邊的1已全部標(biāo)記，左邊還有若干個(gè)0沒(méi)有標(biāo)記，這說(shuō)明左邊符號(hào)0與右邊符號(hào)1個(gè)數(shù)不等，或者0與1交替出現(xiàn)，則w不屬于L。初始狀態(tài)0011B…圖靈機(jī)M：接受的語(yǔ)言L={0n1n|n>1}例如，識(shí)別輸入串w1=0011的過(guò)程如下：第1步：遇到0，將0改為x并右移x011B…第2步：遇到0，右移x011B…第3步：遇到1，將1改為y并左移x0y1B…第4步：遇到0，左移x0y1B…第5步：遇到x，右移x0y1B…第6步：遇到0，將0改為x并右移xxy1B…x0y1B…xxy1B…第7步：遇到y(tǒng)，右移xxy1B…第8步：遇到1，將1改為y并左移xxyyB…第9步：遇到y(tǒng)，左移xxyyB…xxyyB…第10步：遇到x，右移xxyyB…第11步：遇到y(tǒng)，右移xxyyB…第12步：遇到y(tǒng)，右移xxyyB…xxyyB…第13步：遇到B，停機(jī)xxyyB…RRRLRq0q3q4q2q1B/By/yx/x1/y0/xy/y0/0,y/y0/0,y/y狀態(tài)轉(zhuǎn)換圖q0：初始狀態(tài)。q1：在q0下讀到0，把0改為x，同時(shí)狀態(tài)改為q1，q1下讀到0，不改動(dòng)，只右移。q2：在q1讀到1，把1改為y，同時(shí)狀態(tài)改為q2，向左移。q2下讀到0，不改動(dòng)，繼續(xù)左移，直到讀到x，狀態(tài)改為q0。q3：q0下讀到y(tǒng)，狀態(tài)改為q3。q4：q3下讀到B，狀態(tài)改為q4，q4為終止?fàn)顟B(tài)。RRRLRq0q3q4q2q1B/By/yx/x1/y0/xy/y0/0,y/y0/0,y/y對(duì)應(yīng)的動(dòng)作函數(shù)δ設(shè)計(jì)如下：δ01xyBq0(q1，x，R)－－(q3，y，R)－q1(q1，0，R)(q2，y，L)－(q3，y，R)－q2(q2，0，L)－(q0，x，R)(q2，y，L)－q3－－－(q3，y，R)(q4，B，R)q4－－－－－RRRLRq0q3q4q2q1B/By/yx/x1/y0/xy/y0/0,y/y0/0,y/y識(shí)別輸入串w1=0011的瞬像演變過(guò)程如下：q00011→xq1011→x0q111→xq20y1→q2x0y1→xq00y1→xxq1y1→xxyq11→xxq2yy→xq2xyy→xxq0yy→xxyq3y→xxyyq4B→xxyyBq4進(jìn)入終止?fàn)顟B(tài)q4，圖靈機(jī)M停機(jī)并接受輸入串w1。RRRLRq0q3q4q2q1B/By/yx/x1/y0/xy/y0/0,y/y0/0,y/y識(shí)別輸入串w2=011的瞬像演變過(guò)程如下：q0011→xq111→q2xy1→xq0y1→xyq31由于δ(q3，1)無(wú)定義，而q3不屬于終止?fàn)顟B(tài)，所以停機(jī)但不接受w2。RRRLRq0q3q4q2q1B/By/yx/x1/y0/xy/y0/0,y/y0/0,y/y圖靈機(jī)不僅可以作為語(yǔ)言識(shí)別器，還可以計(jì)算函數(shù)?！纠?.12】設(shè)計(jì)一個(gè)圖靈機(jī)，實(shí)現(xiàn)下面函數(shù)的計(jì)算：解：輸入帶上的初始信息應(yīng)為：輸入帶上用連續(xù)m個(gè)0表示整數(shù)m，m、n的各數(shù)之間用1隔開(kāi)。

實(shí)現(xiàn)這個(gè)函數(shù)計(jì)算的圖靈機(jī)為(Q，{0，1}，{0，1，B}，δ，q0，B，Φ)，其中Q={q0，q1，q2，q3，q4，q5，q6}，動(dòng)作函數(shù)δ如下：δ01Bq0(q1，B，R)(q5，B，R)－q1(q1，0，R)(q2，1，R)－q2(q3，1，L)(q2，1，R)(q4，B，L)q3(q3，0，L)(q3，1，L)(q0，B，R)q4(q4，0，L)(q4，B，L)(q6，0，R)q5(q5，B，R)(q5，B，R)(q6，B，R)q6－－－例如，輸入串為0010，的瞬像演變過(guò)程如下：q00010→Bq1010→B0q110→B01q20→B0q311→Bq3011→q3B011→Bq0011→BBq111→BB1q21→BB11q2B→BB1q41→BBq41B→Bq4BBB→B0q6BB這樣計(jì)算出2÷1=1（帶中0的個(gè)數(shù)）。δ01Bq0(q1，B，R)(q5，B，R)－q1(q1，0，R)(q2，1，R)－q2(q3，1，L)(q2，1，R)(q4，B，L)q3(q3，0，L)(q3，1，L)(q0，B，R)q4(q4，0，L)(q4，B，L)(q6，0，R)q5(q5，B，R)(q5，B，R)(q6，B，R)q6－－－

前面定義的圖靈機(jī)只有一條輸入帶，其實(shí)也可以有多條輸入帶，稱之為多帶的圖靈機(jī)。k（k≥1）帶圖靈機(jī)有k條輸入帶和k個(gè)讀寫(xiě)頭，但只有一個(gè)有限狀態(tài)控制器，它掃描k條輸入帶上的當(dāng)前格的信息，才能決定圖靈機(jī)的動(dòng)作。

多帶圖靈機(jī)在識(shí)別語(yǔ)言和計(jì)算函數(shù)方面的能力和單帶圖靈機(jī)是等價(jià)的。一個(gè)語(yǔ)言（函數(shù)）能被一個(gè)多帶圖靈機(jī)接受（計(jì)算）當(dāng)且僅當(dāng)它能被一個(gè)單帶圖靈機(jī)接受（計(jì)算）。2.非確定性圖靈機(jī)

非確定性圖靈機(jī)同確定性圖靈機(jī)的區(qū)別在于它的動(dòng)作函數(shù)δ是一個(gè)多值映射，即在一個(gè)狀態(tài)下，掃描到帶上一格的字符，可以產(chǎn)生多個(gè)動(dòng)作，包括狀態(tài)的變化，在當(dāng)前格上寫(xiě)上新的字符，以及讀寫(xiě)頭的左、右移動(dòng)。即一個(gè)動(dòng)作函數(shù)可以表示為：其中，Ai（1≤i≤k）表示移動(dòng)方向，取L或R。例如，圖靈機(jī)M=(Q，∑，Γ，δ，q0，B，F(xiàn))，其中q0是初始狀態(tài)，q1是終止?fàn)顟B(tài)，動(dòng)作函數(shù)δ如下：δ(q0，B)=(q0，1，R)δ(q0，B)=(q0，B，L)δ(q0，B)=(q1，B，R)δ(q0，1)=(q0，1，L)它是一個(gè)不確定圖靈機(jī)，可以對(duì)輸入的空帶寫(xiě)下任意長(zhǎng)的1段后停機(jī)。從中看出，對(duì)于一個(gè)輸入串而言，可能存在著若干個(gè)演變過(guò)程，其中任何一個(gè)演變過(guò)程最后導(dǎo)致一個(gè)終止?fàn)顟B(tài)，則這個(gè)輸入串就被非確定性圖靈機(jī)接受。同樣，也可以定義多帶非確定性圖靈機(jī)。對(duì)于任意一個(gè)非確定性圖靈機(jī)M，存在一個(gè)確定性圖靈機(jī)M'，使得它們的語(yǔ)言相等，即L(M)=L(M')。3.圖靈機(jī)的停機(jī)問(wèn)題與可計(jì)算性度量一個(gè)圖靈機(jī)并不是對(duì)任何輸入都能停機(jī)。一般來(lái)說(shuō)，一個(gè)圖靈機(jī)M對(duì)一個(gè)輸入串w的工作過(guò)程可能遇到三種情況：（1）進(jìn)入終止?fàn)顟B(tài)，這時(shí)M停機(jī)，并接受w。（2）未進(jìn)入終止?fàn)顟B(tài)，但δ無(wú)定義，此時(shí)M停機(jī)，但不接受w。（3）一直不進(jìn)入終止?fàn)顟B(tài)，且δ一直有定義。這時(shí)進(jìn)入死循環(huán)，M永不停機(jī)。

可計(jì)算函數(shù)與可計(jì)算語(yǔ)言的定義與圖靈機(jī)的停機(jī)問(wèn)題有密切的關(guān)系。若一個(gè)語(yǔ)言被一個(gè)圖靈機(jī)M接受，且對(duì)任意輸入串w，M都停機(jī)，稱之為遞歸語(yǔ)言。一個(gè)語(yǔ)言是可計(jì)算的，當(dāng)且僅當(dāng)它是一個(gè)遞歸語(yǔ)言。同樣，一個(gè)函數(shù)是可計(jì)算的，當(dāng)且僅當(dāng)它是完全遞歸函數(shù)，即存在圖靈機(jī)M實(shí)現(xiàn)其計(jì)算功能，對(duì)于任意輸入，M都能停機(jī)。

從根本上說(shuō)，一個(gè)算法就是一個(gè)確定的、對(duì)任意輸入都停機(jī)的圖靈機(jī)。

確定性圖靈機(jī)是現(xiàn)代電子計(jì)算機(jī)的理論模型。

一個(gè)對(duì)任意輸入都停機(jī)的確定圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可解的問(wèn)題，必然存在多項(xiàng)式時(shí)間復(fù)雜度的計(jì)算機(jī)求解算法。

一個(gè)算法實(shí)質(zhì)上就是一個(gè)以任何輸入都停機(jī)的圖靈機(jī)，因此已經(jīng)找到的多項(xiàng)式時(shí)間界的計(jì)算機(jī)算法的問(wèn)題都屬于P類問(wèn)題。11.2P類和NP類問(wèn)題

非確定性圖靈機(jī)只是一種理論上的計(jì)算模型。不確定圖靈機(jī)可解的問(wèn)題，雖然也可以用確定性圖靈機(jī)求解，但時(shí)間上的耗費(fèi)（或說(shuō)求解步數(shù)）是不一樣的。

用非確定性圖靈機(jī)以多項(xiàng)式時(shí)間界可求解的問(wèn)題，用確定性圖靈機(jī)不能保證在多項(xiàng)式時(shí)間界內(nèi)可求解，但用確定性圖靈機(jī)以指數(shù)時(shí)間界是肯定可以求解的。

用確定性圖靈機(jī)以多項(xiàng)式時(shí)間界可解的問(wèn)題稱為P類問(wèn)題，P指確定性圖靈機(jī)上的具有多項(xiàng)式算法的問(wèn)題集合。

用非確定性圖靈機(jī)以多項(xiàng)式時(shí)間界可解的問(wèn)題稱為NP類問(wèn)題，NP指非確定性圖靈機(jī)上具有多項(xiàng)式算法的問(wèn)題集合，這里N是不確定的意思。

“P=NP？”這個(gè)問(wèn)題，作為理論計(jì)算機(jī)科學(xué)的核心問(wèn)題，其聲名早已經(jīng)超越了這個(gè)領(lǐng)域。

它是Clay研究所的七個(gè)百萬(wàn)美元大獎(jiǎng)問(wèn)題之一，在2006年國(guó)際數(shù)學(xué)家大會(huì)上，它是某個(gè)1小時(shí)講座的主題。

NP問(wèn)題的代表問(wèn)題之一是旅行商旅行（TSP）問(wèn)題。目前發(fā)現(xiàn)的NP問(wèn)題還有很多，如布爾表達(dá)式的可滿足性問(wèn)題、圖的頂點(diǎn)覆蓋問(wèn)題和背包問(wèn)題等等。NPC（NP-completeness）的概念表明找到某個(gè)問(wèn)題的有效算法至少和找NP中所有問(wèn)題的有效算法一樣難。

這里的有效性的含義是指為求解問(wèn)題設(shè)計(jì)的算法的時(shí)間為多項(xiàng)式級(jí)的。11.3NPC問(wèn)題設(shè)L1

，L2

為兩個(gè)語(yǔ)言，若存在映射f：