保持空間復(fù)雜性的算法組合

摘 要:分析了組合兩種算法所需的空間復(fù)雜度在何種情況下為原算法的空間復(fù)雜度之和的問(wèn)題，即空間復(fù)雜度的保持問(wèn)題。通過(guò)形式化oracle查詢方式，證明了在后續(xù)oracle查詢和前面所有的oracle回復(fù)都不相關(guān)，即非適應(yīng)性查詢情況下，算法組合將保持空間復(fù)雜性，但在適應(yīng)性查詢情況時(shí)不一定成立。

關(guān)鍵詞:算法組合; 空間復(fù)雜性; 庫(kù)克歸約; 預(yù)言機(jī)查詢

中圖分類號(hào):TP301.5;TP301.6文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)06-2020-04

doi:10.3969/j.issn.1001-3695.2010.06.005

Space complexity preserving algorithms composition

SHI Hong-song， QIN Zhi-guang

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 611731， China)

Abstract:This work considered the space complexity preserving problem， that was under which conditions the space comple-xity of composing two algorithms will be the sum of the space complexity of the two original algorithms. By formalizing the ways of oracle queries， this paper proved that the space complexity would preserve when oracle queries were non-adaptive， i.e.， the oracle queries were independent of the past oracle answers， but space complexity would not preserve in the adaptive case.

Key words:algorithms composition; space complexity; Cook reduction; oracle queries

0 引言

計(jì)算復(fù)雜性理論通常使用各種歸約(reduction)關(guān)系來(lái)分析問(wèn)題之間的相對(duì)難度和可解性。問(wèn)題B可以Cook歸約(或多項(xiàng)式時(shí)間turing歸約)到問(wèn)題A，是指存在一個(gè)算法MBMA通過(guò)oracle方式查詢問(wèn)題A的解決算法MA可以在確定性多項(xiàng)式時(shí)間內(nèi)解決問(wèn)題B。Cook歸約關(guān)系體現(xiàn)了問(wèn)題的可解性和相對(duì)困難性，但并沒(méi)有考慮處理oracle查詢的時(shí)間和空間復(fù)雜性，因?yàn)樗俣ㄟ@些oracle查詢和回復(fù)是可以在零空間(通過(guò)oracle帶)及單位時(shí)間內(nèi)獲得的。

1 問(wèn)題描述及研究背景

1.1 算法組合的復(fù)雜度

如果問(wèn)題B可以Cook歸約到問(wèn)題A，則通過(guò)組合MBMA和MA可以構(gòu)造出一個(gè)無(wú)須oracle查詢而解決問(wèn)題B的算法M:M模擬MBMA處理輸入實(shí)例x;當(dāng)MBMA需要查詢MA時(shí)，構(gòu)造出相應(yīng)的查詢內(nèi)容，并調(diào)用MA處理該查詢;當(dāng)MA輸出相應(yīng)的回復(fù)后，再模擬MBMA處理回復(fù)內(nèi)容。MBMA的后續(xù)查詢也按上述過(guò)程處理，直至MBMA結(jié)束運(yùn)行。顯然M能正確地模擬MBMA解決問(wèn)題A，且M的時(shí)間復(fù)雜度為O(ktA+tB)。其中tB為MBMA的時(shí)間復(fù)雜度，tA為MA處理oracle查詢的時(shí)間復(fù)雜度，而k為oracle查詢次數(shù)。顯然當(dāng)tA、tB都是n的多項(xiàng)式時(shí)，M也是一個(gè)多項(xiàng)式時(shí)間算法。

本文主要研究隱含在Cook歸約關(guān)系中的空間復(fù)雜性問(wèn)題。筆者稱空間復(fù)雜度為O(sA+sB)的算法組合保持了MA和MBMA的空間復(fù)雜度。其中sA、sB分別為MA、MBMA的空間復(fù)雜度。不難驗(yàn)證，當(dāng)sA、sB都是n的多項(xiàng)式時(shí)，由Cook歸約的性質(zhì)，查詢和回復(fù)的長(zhǎng)度也都是n的多項(xiàng)式，否則MBMA不可能是多項(xiàng)式時(shí)間算法，但M的空間復(fù)雜度是否為O(sA+sB)仍取決于查詢和回復(fù)的長(zhǎng)度。而當(dāng)sA、sB都是O(log n)時(shí)，由于oracle查詢和回復(fù)的長(zhǎng)度可能為上界2O(sB(n))=O(n)，M可能不會(huì)保持空間復(fù)雜性。

本文將證明如果MBMA只作一次oracle查詢，或所有查詢之間滿足非適應(yīng)性條件時(shí)(即后一次查詢和前面所有的查詢回復(fù)都不相關(guān))，可以構(gòu)造保持空間復(fù)雜度的算法組合而無(wú)論查詢和回復(fù)的長(zhǎng)度及次數(shù)為多少(滿足上界2O(sB(n)))，如定理3。但若oracle查詢是適應(yīng)性的情況時(shí)，只有當(dāng)查詢和回復(fù)其中之一的長(zhǎng)度為O(sB)時(shí)才能構(gòu)造保持空間復(fù)雜度的算法組合，如定理1、2;而在兩者長(zhǎng)度都嚴(yán)格地大于sB時(shí)(即為ω(sB)時(shí))是否存在此類算法組合仍無(wú)法確定，如定理3。本文的證明主要使用了以時(shí)間換取空間的策略。

1.2 研究現(xiàn)狀

一般地，如果問(wèn)題B可對(duì)數(shù)空間歸約[1](log-space reduction)到問(wèn)題A，則當(dāng)問(wèn)題A是對(duì)數(shù)空間可解時(shí)，問(wèn)題B也是對(duì)數(shù)空間可解的。該結(jié)論的證明采用了以時(shí)間換空間的策略。但對(duì)數(shù)空間歸約(可認(rèn)為)是一種特殊的Cook歸約(對(duì)數(shù)空間歸約只針對(duì)判定問(wèn)題，如定義1)，本文將利用以時(shí)間換空間的策略解決更廣泛的搜索問(wèn)題歸約的復(fù)雜性。在證明無(wú)向圖兩點(diǎn)連接性問(wèn)題是否對(duì)數(shù)空間可解的過(guò)程中，Aleliunas等人[2]提出的通用遍歷序列思想和Reingold[3]對(duì)此問(wèn)題的證明都是設(shè)計(jì)對(duì)數(shù)空間算法組合的過(guò)程。文獻(xiàn)[3]隱含了本文的某些結(jié)論，但并沒(méi)有像本文一樣作一般性的分析。 Applebaum等人[4]研究了如何在復(fù)雜度內(nèi)設(shè)計(jì)單向函數(shù)和偽隨機(jī)生成器。由于算法是對(duì)數(shù)空間算法，這也可認(rèn)為是研究如何設(shè)計(jì)保持對(duì)數(shù)空間復(fù)雜度的算法組合。總的來(lái)說(shuō)，上述研究現(xiàn)狀和本文的主要區(qū)別在于:本文不是研究如何為具體的問(wèn)題設(shè)計(jì)保持空間復(fù)雜度的算法，而是通過(guò)分析多次查詢的相關(guān)性研究一般情況下對(duì)Cook歸約算法進(jìn)行組合的空間復(fù)雜性問(wèn)題。

此外，對(duì)于組合過(guò)程是否保持算法其他特性的研究也很普遍。例如在隨機(jī)算法(randomized algorithms)[5]研究中，為提高BPP算法的準(zhǔn)確性(即soundness和completeness)，通常采用不同的randomness多次運(yùn)行同一算法，再?gòu)乃械妮敵鲋羞x擇出現(xiàn)次數(shù)最多的結(jié)果作為最終輸出。采用這一策略可將失敗概率從接近2-1降低到2-O(n)，從而提高了算法的準(zhǔn)確性(采用Chernoff bound等分析方法)。這實(shí)際上提供了一個(gè)如何設(shè)計(jì)失敗概率為輸入規(guī)模負(fù)指數(shù)的算法組合的方法。在交互式證明協(xié)議(如interactive proof， zero-knowledge proof等)的設(shè)計(jì)中，也通常采用這種策略提高準(zhǔn)確性[6]。不過(guò)雖然一般的串行組合有效，但是并行和并發(fā)組合卻可能無(wú)法保持協(xié)議的安全性(如zero-knowledge)，在安全多方協(xié)議[7]的研究中也存在類似問(wèn)題。此外，PCP定理[8]的證明過(guò)程本質(zhì)上也是一個(gè)保持常數(shù)查詢長(zhǎng)度的算法組合設(shè)計(jì)過(guò)程。

2 計(jì)算模型

2.1 多帶圖靈機(jī)(Turing machine)模型

本文將算法的計(jì)算模型形式化為一個(gè)三帶確定型圖靈機(jī)M=(Q，Σ，Γ，δ，qstart，qhalt)。它包括一條只讀的輸入帶、一條只寫(xiě)的輸出帶和一條可讀寫(xiě)的工作帶。其中輸出帶探頭只能向右單向移動(dòng)，其他兩條數(shù)據(jù)帶的探頭可左右移動(dòng)。每條數(shù)據(jù)帶都由無(wú)限個(gè)數(shù)據(jù)格組成，并向右延伸。在上述定義中，Q為M的狀態(tài)集合，兩個(gè)特殊狀態(tài)qstart，qhalt∈Q分別表示開(kāi)始和停機(jī)狀態(tài);Σ={0，1}為輸入字母表;Γ=Σ∪{#，⊥}表示工作帶字母表。其中#表示數(shù)據(jù)分隔符，而⊥表示停機(jī)符，只用于輸出帶。

M的計(jì)算過(guò)程由一系列可分的步驟組成，每一步都是由當(dāng)前的輸入帶和工作帶探頭位置、工作帶內(nèi)容及狀態(tài)決定的，稱它們組成的四元組為圖靈機(jī)的即時(shí)配置。相繼步驟的轉(zhuǎn)換是通過(guò)計(jì)算轉(zhuǎn)移函數(shù)δ來(lái)實(shí)現(xiàn)的。δ以當(dāng)前狀態(tài)及輸入帶和工作帶探頭所指內(nèi)容為輸入，產(chǎn)生新的狀態(tài)、工作帶和輸出帶內(nèi)容及三帶探頭的移動(dòng)方式，描述為δ:Q×Γ2→Q×Γ2×{0，1，-1}2×{0，1}。其中0表示不動(dòng)，-1/1分別表示向左/右移動(dòng)一格。關(guān)于圖靈機(jī)的更多工作細(xì)節(jié)請(qǐng)參見(jiàn)文獻(xiàn)[1]。若無(wú)特別說(shuō)明下文所談圖靈機(jī)均為三帶確定型圖靈機(jī)。

定義1 判定問(wèn)題(decision problem)A為滿足某特定條件的子集SA{0，1}*;搜索問(wèn)題 (search problem)A為滿足某特定條件的二元關(guān)系RA{0，1}*×{0，1}*。圖靈機(jī)M能解決問(wèn)題A是指:M最終停機(jī)，且當(dāng)輸入為x時(shí)，若A是判定問(wèn)題，當(dāng)x∈SA時(shí)輸出1，否則輸出0;若A是搜索問(wèn)題，且{y∶(x，y)∈RA}不為空，則輸出一個(gè)解y，否則輸出⊥。

定義2 圖靈機(jī)M的時(shí)間復(fù)雜度為函數(shù)t∶N→N。其中:t(n)是當(dāng)輸入長(zhǎng)度為n時(shí)，M完成計(jì)算所經(jīng)歷的最大步數(shù)。M的空間復(fù)雜度定義為函數(shù)s∶N→N，其中s(n)是當(dāng)輸入長(zhǎng)度為n時(shí)，M完成計(jì)算所使用的工作帶的最大長(zhǎng)度。

顯然，如果一個(gè)圖靈機(jī)能停機(jī)，則其計(jì)算過(guò)程中不會(huì)出現(xiàn)兩個(gè)相同的配置，從而運(yùn)行時(shí)間是由不同的配置數(shù)決定的。不難驗(yàn)證，若M的空間復(fù)雜度為s(n)≥log n，其時(shí)間復(fù)雜度上界將為2O(s(n))(具體證明可見(jiàn)文獻(xiàn)[1])。

2.2 帶oracle的圖靈機(jī)

定義3[2] 帶oracleO的圖靈機(jī)MO是一種特殊類型的(五帶)圖靈機(jī)，它具有兩條特殊的數(shù)據(jù)帶，即oracle查詢帶、回復(fù)帶和兩個(gè)特殊的狀態(tài)qquery和qresponse，并可以與一個(gè)外部設(shè)備O(稱為oracle)交互。當(dāng)MO進(jìn)入qquery狀態(tài)時(shí)，將寫(xiě)入一個(gè)查詢至oracle查詢帶，并在下一步進(jìn)入qresponse狀態(tài)讀取由O寫(xiě)入oracle回復(fù)帶的內(nèi)容。如果O也是一個(gè)圖靈機(jī)，可以認(rèn)為MO的oracle查詢帶和回復(fù)帶分別為O的輸入和輸出帶。

定義3 假定無(wú)論oracle查詢和回復(fù)有多長(zhǎng)，MO總能在單步時(shí)間內(nèi)提交oracle查詢，同時(shí)O也總能在MO的單步時(shí)間內(nèi)作出正確的回復(fù)。

定義4 若圖靈機(jī)MA能解決問(wèn)題A，且將MA當(dāng)成oracle可設(shè)計(jì)另一個(gè)圖靈機(jī)MBMA在確定性多項(xiàng)式時(shí)間內(nèi)解決問(wèn)題B，則稱問(wèn)題B可Cook歸約到問(wèn)題A，表示為B≤c A。其中MBMA的空間復(fù)雜度仍定義為其工作帶所使用的最大長(zhǎng)度(而不包括oracle帶的使用長(zhǎng)度)。

不難驗(yàn)證如果B≤c A，且MA也是一個(gè)多項(xiàng)式時(shí)間的圖靈機(jī)時(shí)，可以通過(guò)1.1節(jié)描述的方法模擬MA和MBMA構(gòu)造出一個(gè)多項(xiàng)式時(shí)間的圖靈機(jī)解決問(wèn)題B。然而定義3忽視了oracle查詢和回復(fù)的空間復(fù)雜性。例如，當(dāng)sA和sB都為O(log n)時(shí)，由Cook歸約的性質(zhì)，B是多項(xiàng)式時(shí)間可解的，說(shuō)明一定可以構(gòu)造空間復(fù)雜度為O(nc)的圖靈機(jī)解決問(wèn)題B，但B是否可以在O(log n)復(fù)雜度內(nèi)解決仍不太確定。下文將對(duì)此問(wèn)題作更多分析。

3 算法組合的空間復(fù)雜性

設(shè)圖靈機(jī)MA的空間復(fù)雜度為sA，它是MA輸入長(zhǎng)度的函數(shù)。圖靈機(jī)MBMA的空間復(fù)雜度為sB(n)，其oracle查詢和回復(fù)的長(zhǎng)度分別為q(n)和r(n)。其中n是MBMA的輸入長(zhǎng)度。本章將分析算法組合的空間復(fù)雜性和sA、sB(n)、q(n)及r(n)等的相關(guān)性。

通常MBMA的輸入帶內(nèi)容也可能是oracle查詢的一部分，即MA在處理查詢時(shí)也將訪問(wèn)這些內(nèi)容。由于輸入帶內(nèi)容不占用額外的工作帶空間，下文假定q(n)僅表示不含MBMA輸入帶內(nèi)容的查詢長(zhǎng)度。

3.1 Oracle查詢方式

設(shè)MBMA在運(yùn)行過(guò)程中要作k≥1次oracle查詢，記這些查詢?yōu)閝1，…，qk，相應(yīng)的回復(fù)為r1，…，rk。為討論方便，下文(除3.4節(jié)的遞歸查詢外)假定各次查詢之間存在線性時(shí)序關(guān)系，即MBMA總在獲得ri-1后才提出查詢qi(i>1)，因而可將MBMA的運(yùn)行過(guò)程按查詢劃分為k+1個(gè)階段。MBMA在最后一個(gè)階段(即第k+1個(gè)階段)完成計(jì)算，在前k個(gè)階段構(gòu)造和處理oracle查詢，即通過(guò)前一次的oracle回復(fù)、配置和輸入帶內(nèi)容計(jì)算出新的查詢和配置內(nèi)容。形式上，第1≤i≤k個(gè)階段的工作表示為

(qi，ci)=(f(i)1(ri-1，ci-1，x)，f(i)2(ri-1，ci-1，x))(1)

其中:ci-1為MBMA在第i-1個(gè)階段的即時(shí)配置，x∈{0，1}n為輸入帶內(nèi)容，且函數(shù)f(i)1、 f(i)2分別表示第i次查詢和配置的編碼函數(shù)。展開(kāi)式(1)，可知qi，ci均為ri-1，ri-2，…，r1，c0及x的函數(shù);r0為空串，因此稱這多次查詢?yōu)檫m應(yīng)性查詢。下文將k=1的情況視為適應(yīng)性查詢的特例。

一般地，編碼函數(shù)f(i)1、 f(i)2的功能在不同的階段可能不同，而當(dāng)MBMA的運(yùn)行過(guò)程是由一系列迭代過(guò)程組成時(shí)，這些函數(shù)在整個(gè)計(jì)算過(guò)程中都是相同的。不過(guò)由于這種相等關(guān)系不會(huì)影響下文的分析過(guò)程，為簡(jiǎn)化符號(hào)，下文約定f(i)1=…=f(1)1=f1，且f(i)2=…=f(1)2=f2。

若qi不依賴于ri-1，ri-2，…，r1，稱這k次查詢是非適應(yīng)性的，此時(shí)

(qi，ci)=(f ′1(c′i-1，x)，f2(ri-1，ci-1，x))(2)

其中:c′i-1=f′2(c′i-2，x)為ci-1中不依賴于ri-2，…，r1的部分，滿足c′0=c0，且f′1、 f′2為不依賴于ri-2，…，r1的下一次查詢和配置的編碼函數(shù)。展開(kāi)qi可得qi=f′1(f′i-12(c0，x))。其中f′i-12表示f′2的i-1次迭代函數(shù)，f′1(f′02(c0，x))=f′1(c0，x)。這說(shuō)明所有的非適應(yīng)性查詢可在第一次查詢前完全構(gòu)造出來(lái)。

顯然適應(yīng)性查詢要比非適應(yīng)性查詢功能更強(qiáng)，即通過(guò)適應(yīng)性查詢能解決的問(wèn)題不一定能在同等的空間復(fù)雜度內(nèi)通過(guò)非適應(yīng)性查詢解決，反之一定成立。

3.2 空間有效的組合方法

由空間復(fù)雜度和時(shí)間復(fù)雜度的關(guān)系，若圖靈機(jī)MBMA的空間復(fù)雜度為sB(n)=O(log n)，q(n)和r(n)的長(zhǎng)度上界都將為2O(sB(n))。當(dāng)sA(q(n))也為2O(sB(n))時(shí)，1.1節(jié)描述的基本組合方法的空間復(fù)雜度上界為O(sB(n)+sA(q(n))+q(n)+r(n))=2O(sB(n))。若sB(n)=w(log n)，該組合方法獲得的空間復(fù)雜度將可能為n的超多項(xiàng)式，這通常被認(rèn)為是無(wú)效的算法。構(gòu)造保持空間復(fù)雜性的算法組合的困難性在于當(dāng)q(n)和r(n)都為ω(sB(n))時(shí)，無(wú)法保證能在O(sB(n)+sA(q(n)))復(fù)雜度內(nèi)完整地存儲(chǔ)查詢和回復(fù)。由于圖靈機(jī)運(yùn)行過(guò)程的局部性特征，以下的以時(shí)間換取空間的策略[1]能在一定程度上解決該問(wèn)題。

定理1 若B≤c A，則當(dāng)q(n)=2O(sB(n))且r(n)=O(sB(n))時(shí)，可構(gòu)造空間復(fù)雜度為s(n)=O(sB(n)+sA(q(n)))的算法組合解決問(wèn)題B。

證明 先考慮k=1的情況。當(dāng)輸入x∈{0，1}n時(shí)，M模擬運(yùn)行MBMA并保存初始配置c0。注意:由于q(n)=2O(sB(n))，M無(wú)法在空間O(sB(n))內(nèi)完整地存儲(chǔ)q1，但M可以執(zhí)行以下算法以避免這個(gè)問(wèn)題。當(dāng)MBMA需要查詢oracle時(shí)，M假定q1已保存在特定的位置并模擬MA處理該查詢。當(dāng)MA需要讀取q1的第l個(gè)符號(hào)時(shí)，保存MA的即時(shí)配置cA，并載入c0模擬MBMB計(jì)算f1(c0，x)以獲取q1的第l個(gè)符號(hào)(M只存儲(chǔ)這個(gè)符號(hào));然后再載入cA返回模擬MA，MA的回復(fù)r1均保存在M的工作帶上。上述過(guò)程可以在不預(yù)先構(gòu)造完整查詢內(nèi)容的情況下模擬MA計(jì)算oracle回復(fù)，完成了對(duì)MBMB第一階段的模擬;此后計(jì)算配置C1=f2(c0，x)并模擬MBMA的第二個(gè)階段直至結(jié)束。

容易驗(yàn)證M實(shí)現(xiàn)了MBMA的功能。由于c1可重用計(jì)算q1所使用的存儲(chǔ)空間，M在計(jì)算過(guò)程中主要存儲(chǔ)(c0，c1，cA，r1)，M的空間復(fù)雜度為s(n)=2sB(n)+sA(q(n))+r(n)+λ(n)。其中λ(n)=log(2sB(n)+q(n)+sA(q(n))+r(n))為存儲(chǔ)工作帶探頭位置所帶來(lái)的開(kāi)銷。

考慮k>1的非適應(yīng)性查詢情況。在第1≤i≤k個(gè)階段，M需要計(jì)算(qi，ci，c′i，ri)。類似于上述k=1的情況，qi也無(wú)須在調(diào)用MA前完整地計(jì)算出來(lái)。由式(2)，M先利用(ci-1，ri-1)和c′i-1計(jì)算出ci=f2(ri-1，ci-1，x)和c′i=f′2(c′i-1，x)，再在MA需要qi時(shí)計(jì)算f′1(c′i-1，x)。由于ri可重用ri-1的空間，M在每個(gè)階段主要存儲(chǔ)(ci，ci-1，cA，ri，c′i，c′i-1)，具有空間復(fù)雜度s(n)=4sB(n)+sA(q(n))+r(n)+λ′(n)。其中λ′(n)=log(4sB(n)+q(n)+sA(q(n))+r(n))為存儲(chǔ)工作帶探頭位置所帶來(lái)的開(kāi)銷。

考慮k>1的適應(yīng)性查詢情況與非適應(yīng)情況類似，為了在第1≤i≤k個(gè)階段計(jì)算出ri需要使用上述處理k=1的方法。由式(1)，由于計(jì)算qi需要(ci-1，ri-1)的值，從而在計(jì)算ri的過(guò)程中(ci，ri)不能覆蓋(ci-1，ri-1)。該算法組合的每個(gè)迭代過(guò)程主要存儲(chǔ)(ci，cA，ri，ci-1，ri-1)，共需要存儲(chǔ)空間s(n)=2sB(n)+sA(q(n))+2r(n)+λ″(n)。其中λ″(n)=log(2sB(n)+q(n)+sA(q(n))+2r(n))為存儲(chǔ)工作帶探頭位置所帶來(lái)的開(kāi)銷。

綜合上述各情況可得s(n)=O(sB(n)+sA(q(n))。得證。

定理2 若B≤c A，則當(dāng)q(n)=O(sB(n))，r(n)=2O(sB(n))，時(shí)，可構(gòu)造空間復(fù)雜度為s(n)=O(sB(n)+sA(q(n)))的算法組合解決問(wèn)題B。

證明 基本思路也是使用以時(shí)間換空間的方法在MBMA需要讀取oracle回復(fù)時(shí)調(diào)用MA即時(shí)生成所需內(nèi)容，而不存儲(chǔ)完整的oracle回復(fù)。先考慮k=1的情況。當(dāng)輸入x∈{0，1}n時(shí)，M模擬運(yùn)行MBMA。由于q(n)=O(sB(n))，該過(guò)程將構(gòu)造并存儲(chǔ)(q1，c1)。當(dāng)MBMA需要查詢oracle時(shí)，M假定MA已輸出回復(fù)r1至特定的位置，而繼續(xù)模擬運(yùn)行MBMA的第二個(gè)運(yùn)行階段。當(dāng)MBMA需要讀取r1的第l個(gè)符號(hào)時(shí)，M模擬MA處理q1直至MA輸出r1的第l個(gè)符號(hào)，再返回對(duì)MBMA的模擬。易知M可完全模擬MBMA解決問(wèn)題B。該過(guò)程的空間復(fù)雜度為s(n)=sB(n)+sA(q(n))+q(n)+λ(n)。其中λ(n)=log(sB(n))+q(n)+sA(q(n))+r(n)。

考察k>1且各查詢?yōu)榉沁m應(yīng)性的情況。由于無(wú)法在空間O(sB(n))內(nèi)存儲(chǔ)ri，MBMA第1≤i≤k個(gè)階段的工作主要用于計(jì)算(ci，qi，c′i)而無(wú)須存儲(chǔ)完整的ri，當(dāng)?shù)趇+1個(gè)階段需要ri時(shí)才按上述k=1的情況處理。具體地說(shuō)，由式(2)計(jì)算ci=f2(ri-1，ci-1，x)需要預(yù)先知道ci-1和ri-1的值，但由于ri-1可通過(guò)(以qi-1為輸入)調(diào)用MA來(lái)計(jì)算，存儲(chǔ)qi-1足以解決問(wèn)題。為了在階段i計(jì)算(ci，qi，c′i)，需要存儲(chǔ)(ci-1，qi-1，c′i-1)。由于qi=f′1(c′i-1，x)和ri-1無(wú)關(guān)，可以在計(jì)算ci后再計(jì)算qi，并重用qi-1的空間。因此總的空間開(kāi)銷為s(n)=4sB(n)+sA(q(n))+q(n)+λ′(n)。其中λ′(n)=log(4sB(n)+q(n)+sA(q(n))+r(n))。

當(dāng)這k>1次查詢非獨(dú)立時(shí)，可以采用與非適應(yīng)性的情況類似的處理辦法在每個(gè)迭代過(guò)程計(jì)算(ci，qi)。由式(1)，這需要存儲(chǔ)(ci-1，qi-1)，在計(jì)算函數(shù)f1、 f2時(shí)，若需要ri-1的某個(gè)符號(hào)時(shí)才利用qi-1調(diào)用MA。由于(ci，qi)的計(jì)算都需要(ci-1，qi-1)，而無(wú)法重用(ci-1，qi-1)占用的空間，其空間復(fù)雜度為s(n)=2sB(n)+sA(q(n))+2q(n)+λ″(n)。其中λ″(n)=log(2sB(n)+2q(n)+sA(q(n))+r(n))。

綜上，可構(gòu)造復(fù)雜度為s(n)=O(sB(n)+sA(q(n)))的算法組合解決問(wèn)題B。

由上述兩個(gè)定理，若M是一個(gè)保持空間復(fù)雜性的算法組合，M的空間復(fù)雜度將由max(sB(n)，sA(q(n)))決定。進(jìn)一步得到下面的推論。

推論1 若B≤c A，則當(dāng)sA(n)、sB(n)都為O(log n)，而q(n)和r(n)其中之一為O(log n)，另一個(gè)為n的多項(xiàng)式時(shí)，問(wèn)題B可以在O(log n)空間內(nèi)解決。

注意上述結(jié)論和查詢次數(shù)k無(wú)關(guān)。下面將證明一個(gè)更一般的結(jié)論。

定理3 若B≤c A，則當(dāng)q(n)=2O(sB(n))，r(n)=2O(sB(n))且MBMA的查詢是非適應(yīng)性方式時(shí)，可構(gòu)造空間復(fù)雜度為s(n)=O(sB(n)+sA(q(n)))的算法組合解決問(wèn)題B。而對(duì)于適應(yīng)性查詢，當(dāng)k不為常數(shù)時(shí)，無(wú)法保證存在這樣的算法組合。

證明 綜合了上述定理1和2使用的策略。考慮k=1的情況，當(dāng)輸入x∈{0，1}n時(shí)，M模擬運(yùn)行MBMA。由于q(n)=2O(sB(n))，M無(wú)法在空間O(sB(n))內(nèi)存儲(chǔ)q1。但M可以假定q1已經(jīng)提交，并得到了相應(yīng)的回復(fù)r1，進(jìn)而模擬MBMA的第二個(gè)階段。具體是，在第一次調(diào)用MA前存儲(chǔ)配置c0;當(dāng)MBMA需要讀取r1的第i個(gè)符號(hào)時(shí)，先保存即時(shí)配置c2(此時(shí)c1是一個(gè)過(guò)渡配置)，并模擬MA處理查詢q1直至輸出r1的第i個(gè)符號(hào)。更進(jìn)一步，由于q1=f1(c0，x)，當(dāng)MA在運(yùn)行期間需要讀取q1的第j個(gè)符號(hào)時(shí)，M保存即時(shí)配置cA，并載入c0計(jì)算q1的第j個(gè)符號(hào);然后再載入cA，以上述方式模擬MA直至輸出r1的第i個(gè)符號(hào)。之后載入c2，模擬MBMA讀取r1的第i個(gè)符號(hào)。重復(fù)上述過(guò)程，直至完成對(duì)MBMA的模擬。這個(gè)組合過(guò)程使用了兩次以時(shí)間換取空間的策略，且需存儲(chǔ)(c0，c2，cA)并計(jì)算q1，由于空間無(wú)法重用，且需要多次計(jì)算f1、 f2，使得其空間復(fù)雜度為s(n)=3sB(n)+sA(q(n))+λ(n)，其中λ(n)=log(3sB(n)+q(n)+sA(q(n))+r(n))。

考察k>1次非適應(yīng)性查詢的情況。由于無(wú)法在空間O(sB(n))內(nèi)存儲(chǔ)qi、ri，MBMA在第i個(gè)階段主要計(jì)算(ci，c′i)而無(wú)須計(jì)算出完整的ri，只有在第i+1個(gè)階段需要該值時(shí)才按上述k=1的情況處理。具體地說(shuō)，由式(2)，ci=f2(ri-1，ci-1，x)=f2(MA(qi-1)，ci-1，x)。其中MA(q)表示以q查詢MA得到的回復(fù)。由于qi-1=f′1(c′i-2，x)，存儲(chǔ)(ci-1，c′i-2)可以計(jì)算出ci=f2(MA(f′1(c′i-2，x))，ci-1，x)及c′i=f′2(c′i-1，x)。總的空間開(kāi)銷為s(n)=6sB(n)+sA(q(n))+λ′(n)。其中:λ′(n)=log(6sB(n)+q(n)+sA(q(n))+r(n))，系數(shù)6是存儲(chǔ)(ci，c′i，ci-1，c′i-1，c′i-2)和計(jì)算f′1帶來(lái)的開(kāi)銷。因此s(n)=O(sB(n)+sA(q(n)))。

考察適應(yīng)性查詢的情況。在第i個(gè)迭代過(guò)程，由式(1)，ci=f2(ri-1，ci-1，x)，即為了計(jì)算ci需要知道ri-1和ci-1。假定ci-1已在第i-1個(gè)階段得到，由于無(wú)法存儲(chǔ)ri-1，需要計(jì)算ri-1=MA(qi-1)=MA(f1(ri-2，ci-2，x))，為此又需要知道ri-2，為計(jì)算ri-2又需要知道ri-3，……。為計(jì)算ci需要計(jì)算所有前i-1個(gè)oracle回復(fù)。當(dāng)i為常數(shù)時(shí)，可以使用處理k=1的方法在空間s(n)=O(sB(n)+sA(q(n)))迭代地求出ci;否則，當(dāng)q(n)=2Θ(sB(n))，r(n)=2Θ(sB(n))時(shí)，由于無(wú)法在O(sB(n)+sA(q(n)))空間內(nèi)存儲(chǔ)所有的ri，上述方法不能構(gòu)造出空間復(fù)雜度為O(sB(n)+sA(q(n)))的算法組合解決問(wèn)題B。

3.3 遞歸調(diào)用和多oracle查詢

如果問(wèn)題A可Cook歸約到更小規(guī)模的同等問(wèn)題并最終可解，就稱問(wèn)題A是遞歸可解的。遞歸可解問(wèn)題體現(xiàn)了一種特殊的適應(yīng)性oracle查詢關(guān)系。在這種oracle查詢中，各次查詢之間不存在線性時(shí)序關(guān)系，而允許一個(gè)查詢還未處理完時(shí)就進(jìn)行另一次查詢，從而使得不同遞歸層次中的某些空間無(wú)法重用。因此，遞歸可解問(wèn)題的空間復(fù)雜性就與遞歸深度及每一層遞歸所使用的空間相關(guān)。容易證明下面的簡(jiǎn)單結(jié)論。

定理4 如果問(wèn)題A是遞歸可解的，且遞歸層次k和每一層遞歸的空間復(fù)雜度sA(n)之間滿足k×sA(n)=O(log n)，則問(wèn)題A是O(log n)空間復(fù)雜度內(nèi)可解的。

注:sA(n)不包括各層遞歸之間可共享的空間，這部分空間可為O(log n)。綜合定理2和4，實(shí)際上證明了Reingold[3]判斷無(wú)向圖兩點(diǎn)連接性的算法是對(duì)數(shù)空間可解的。

上文的討論實(shí)際上只分析了單個(gè)oracle查詢的算法組合，而在實(shí)際應(yīng)用中，很可能為解決一個(gè)問(wèn)題需要查詢多個(gè)oracle。由3.1節(jié)將一個(gè)算法的執(zhí)行過(guò)程按照oracle查詢劃分為不同過(guò)程的方法，本文同樣可以證明當(dāng)各次查詢之間滿足線性時(shí)序關(guān)系時(shí)，也可以得到類似定理1~3的結(jié)論。

4 結(jié)束語(yǔ)

若問(wèn)題B可以Cook歸約到問(wèn)題A，假定相應(yīng)的解決算法為MBMA和MA，本文研究了通過(guò)模擬MBMA和MA為問(wèn)題B設(shè)計(jì)算法組合的空間復(fù)雜性。在oracle查詢?yōu)榉沁m應(yīng)性的情況時(shí)，算法組合將保持oracle查詢算法的空間復(fù)雜性，即O(sB(n)+sA(q(n)))。其中sA(#8226;)、sB(#8226;)分別為MA、MBMA的空間復(fù)雜度，且q(#8226;)為oracle查詢的長(zhǎng)度;當(dāng)oracle查詢和回復(fù)的長(zhǎng)度都為2O(sB(n))時(shí)，在適應(yīng)性查詢情況下是否存在保持空間復(fù)雜性的算法組合仍未知。

后續(xù)工作將研究不同查詢方式的關(guān)系，并論證查詢長(zhǎng)度和適應(yīng)性方式對(duì)規(guī)約強(qiáng)度的影響。

參考文獻(xiàn):

[1]ARORA S， BARAK B. Computational complexity: a modern approach [M].New York:Cambridge University Press，2009.

[2]ALELIUNAS R， KARP R M， LIPTON R J， et al. Random walks， universal traversal sequences， and the complexity of maze problems [C]//Proc of the 20th Annual Symposium on Foundations of Computer Science.Washington DC:IEEE Computer Society，1979:218-223.

[3]REINGOLD O. Undirected st-connectivity in log-space [C]//Proc of the 37th ACM Symposium on Theory of Computing.New York:ACM Press，2005:376-385.

[4]APPLEBAUM B， ISHAI Y， KUSHILEVITZ E. Cryptography in NC0 [J]. SIAM Journal of Computing，2006，36(4):845-888.

[5]MOTWANI R， RAGHAVAN P. Randomized algorithms [M].New York:Cambridge University Press，1995.

[6]GOLDREICH O. The foundations of cryptography:vol 1(busic tools) [M].New York:Cambridge University Press，2004.

[7]CANETTI R. Security and composition of multi-party cryptographic protocols [J]. Journal of Cryptology，2000，13(1):143-202.

[8]DINUR I. The PCP theorem by gap amplification [C]// Proc of the 38th ACM Symposium on Theory of Computing.New York:ACM Press，2006:241-250.