保持空間復雜性的算法組合

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

關鍵詞:算法組合; 空間復雜性; 庫克歸約; 預言機查詢

中圖分類號:TP301.5;TP301.6文獻標志碼:A

文章編號: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 引言

計算復雜性理論通常使用各種歸約(reduction)關系來分析問題之間的相對難度和可解性。問題B可以Cook歸約(或多項式時間turing歸約)到問題A，是指存在一個算法MBMA通過oracle方式查詢問題A的解決算法MA可以在確定性多項式時間內解決問題B。Cook歸約關系體現(xiàn)了問題的可解性和相對困難性，但并沒有考慮處理oracle查詢的時間和空間復雜性，因為它假定這些oracle查詢和回復是可以在零空間(通過oracle帶)及單位時間內獲得的。

1 問題描述及研究背景

1.1 算法組合的復雜度

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

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

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

1.2 研究現(xiàn)狀

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

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

2 計算模型

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

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

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

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

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

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

2.2 帶oracle的圖靈機

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

定義3 假定無論oracle查詢和回復有多長，MO總能在單步時間內提交oracle查詢，同時O也總能在MO的單步時間內作出正確的回復。

定義4 若圖靈機MA能解決問題A，且將MA當成oracle可設計另一個圖靈機MBMA在確定性多項式時間內解決問題B，則稱問題B可Cook歸約到問題A，表示為B≤c A。其中MBMA的空間復雜度仍定義為其工作帶所使用的最大長度(而不包括oracle帶的使用長度)。

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

3 算法組合的空間復雜性

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

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

3.1 Oracle查詢方式

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

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

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

一般地，編碼函數f(i)1、 f(i)2的功能在不同的階段可能不同，而當MBMA的運行過程是由一系列迭代過程組成時，這些函數在整個計算過程中都是相同的。不過由于這種相等關系不會影響下文的分析過程，為簡化符號，下文約定f(i)1=…=f(1)1=f1，且f(i)2=…=f(1)2=f2。

若qi不依賴于ri-1，ri-2，…，r1，稱這k次查詢是非適應性的，此時

(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的下一次查詢和配置的編碼函數。展開qi可得qi=f′1(f′i-12(c0，x))。其中f′i-12表示f′2的i-1次迭代函數，f′1(f′02(c0，x))=f′1(c0，x)。這說明所有的非適應性查詢可在第一次查詢前完全構造出來。

顯然適應性查詢要比非適應性查詢功能更強，即通過適應性查詢能解決的問題不一定能在同等的空間復雜度內通過非適應性查詢解決，反之一定成立。

3.2 空間有效的組合方法

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

定理1 若B≤c A，則當q(n)=2O(sB(n))且r(n)=O(sB(n))時，可構造空間復雜度為s(n)=O(sB(n)+sA(q(n)))的算法組合解決問題B。

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

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

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

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

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

定理2 若B≤c A，則當q(n)=O(sB(n))，r(n)=2O(sB(n))，時，可構造空間復雜度為s(n)=O(sB(n)+sA(q(n)))的算法組合解決問題B。

證明 基本思路也是使用以時間換空間的方法在MBMA需要讀取oracle回復時調用MA即時生成所需內容，而不存儲完整的oracle回復。先考慮k=1的情況。當輸入x∈{0，1}n時，M模擬運行MBMA。由于q(n)=O(sB(n))，該過程將構造并存儲(q1，c1)。當MBMA需要查詢oracle時，M假定MA已輸出回復r1至特定的位置，而繼續(xù)模擬運行MBMA的第二個運行階段。當MBMA需要讀取r1的第l個符號時，M模擬MA處理q1直至MA輸出r1的第l個符號，再返回對MBMA的模擬。易知M可完全模擬MBMA解決問題B。該過程的空間復雜度為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應性的情況。由于無法在空間O(sB(n))內存儲ri，MBMA第1≤i≤k個階段的工作主要用于計算(ci，qi，c′i)而無須存儲完整的ri，當第i+1個階段需要ri時才按上述k=1的情況處理。具體地說，由式(2)計算ci=f2(ri-1，ci-1，x)需要預先知道ci-1和ri-1的值，但由于ri-1可通過(以qi-1為輸入)調用MA來計算，存儲qi-1足以解決問題。為了在階段i計算(ci，qi，c′i)，需要存儲(ci-1，qi-1，c′i-1)。由于qi=f′1(c′i-1，x)和ri-1無關，可以在計算ci后再計算qi，并重用qi-1的空間。因此總的空間開銷為s(n)=4sB(n)+sA(q(n))+q(n)+λ′(n)。其中λ′(n)=log(4sB(n)+q(n)+sA(q(n))+r(n))。

當這k>1次查詢非獨立時，可以采用與非適應性的情況類似的處理辦法在每個迭代過程計算(ci，qi)。由式(1)，這需要存儲(ci-1，qi-1)，在計算函數f1、 f2時，若需要ri-1的某個符號時才利用qi-1調用MA。由于(ci，qi)的計算都需要(ci-1，qi-1)，而無法重用(ci-1，qi-1)占用的空間，其空間復雜度為s(n)=2sB(n)+sA(q(n))+2q(n)+λ″(n)。其中λ″(n)=log(2sB(n)+2q(n)+sA(q(n))+r(n))。

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

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

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

注意上述結論和查詢次數k無關。下面將證明一個更一般的結論。

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

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

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

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

3.3 遞歸調用和多oracle查詢

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

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

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

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

4 結束語

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

后續(xù)工作將研究不同查詢方式的關系，并論證查詢長度和適應性方式對規(guī)約強度的影響。

參考文獻:

[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.