Savitchs teorem

I beräkningskomplexitetsteorin ger Savitchs teorem , bevisad av Walter Savitch 1970, ett förhållande mellan deterministisk och icke-deterministisk rymdkomplexitet . Den anger att för alla funktioner $f\in \Omega (\log(n))$ ,

${\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right ).$

Med andra ord, om en icke-deterministisk Turing-maskin kan lösa ett problem med hjälp av ${\displaystyle f(n)}-$ rymden, kan en deterministisk Turing-maskin lösa samma problem i kvadraten av det utrymmesbundna. Även om det verkar som att icke-determinism kan ge exponentiella vinster i tid (som formaliserats i den obevisade exponentiella tidshypotesen ), visar Savitchs teorem att den har en markant mer begränsad effekt på utrymmeskraven.

Bevis

Beviset förlitar sig på en algoritm för STCON , problemet med att avgöra om det finns en väg mellan två hörn i en riktad graf , som går i $O\left((\log n) ^{2}\right)$ utrymme för $n$ hörn. Grundidén med algoritmen är att rekursivt lösa ett något mer generellt problem, att testa förekomsten av en väg från en vertex $s$ till en annan vertex $t$ som använder högst $k$ edges, för en parameter $k$ som anges som indata. STCON är ett specialfall av detta problem där $k$ är inställd tillräckligt stor för att inte lägga någon begränsning på vägarna (till exempel lika med det totala antalet hörn i grafen, eller något större värde). För att testa för en $k$ -kantsväg från $s$ till $t$ , kan en icke-deterministisk algoritm gissa identiteten för en mittpunkt $u$ i sökvägen, och sök rekursivt efter vägar med halva längden från $s$ till $u$ och från $u$ till $t$ . Denna algoritm kan uttryckas i pseudokod (i Python- syntax) enligt följande:

    
    
         

     
    
       0
           
       
            
       
                   
             
      def  stcon  (  s  ,  t  )  ->  bool  :  """Testa om det finns en väg av någon längd från s till t"""  return  k_edge_path  (  s  ,  t  ,  n  )  # n är antalet hörn  def  k_edge_path  (  s  ,  t  ,  k  )  ->  bool  :  """Testa om en väg med längd som högst k existerar från s till t"""  om  k  ==  :  return  s  ==  t  if  k  ==  1  :  return  (  s  ,  t  )  i  kanter  för  u  i  hörn  :  om  k_edge_path  (  s  ,  u  ,  floor  (  k  /  2  ))  och  k_edge_path  (  u  ,  t  ,  ceil  (  k  /  2  )):  return  True  return  False 

Eftersom varje rekursivt anrop halverar parametern $k$ , är antalet nivåer av rekursion $\lceil \log _{2}n\rceil$ . Varje nivå kräver $O(\log n)$ lagringsbitar för dess funktionsargument och lokala variabler : $k$ och hörnen $s$ , $t$ och $u$ kräver $\lceil \log _{2}n\rceil$ bitar vardera. Den totala hjälprymdskomplexiteten är alltså $O\left((\log n)^{2}\right)$ . Ingångsgrafen anses vara representerad i ett separat skrivskyddat minne och bidrar inte till denna hjälprymdsbegränsning. Alternativt kan den representeras som en implicit graf . Även om det beskrivs ovan i form av ett program på ett högnivåspråk, kan samma algoritm implementeras med samma asymptotiska utrymme bundet på en Turing-maskin .

Denna algoritm kan appliceras på en implicit graf vars hörn representerar konfigurationerna av en icke-deterministisk Turing-maskin och dess tejp, som körs inom ett givet utrymme f ( $displaystyle f(n)}$ . Kanterna på denna graf representerar maskinens icke-deterministiska övergångar, $s$ är satt till maskinens initiala konfiguration och $t$ är satt till en speciell vertex som representerar alla accepterande stopptillstånd. I det här fallet returnerar algoritmen sant när maskinen har en icke-deterministisk acceptansväg, och annars falskt. Antalet konfigurationer i denna graf är ${\displaystyle O(2^{f(n)})} ,$ av vilket det följer att applicering av algoritmen på denna implicita graf använder mellanslag $O(f(n)^{2})$ . Genom att bestämma anslutningsmöjligheter i en graf som representerar icke-deterministiska Turing-maskinkonfigurationer, kan man bestämma medlemskap i det språk som känns igen av den maskinen, i rymden som är proportionell mot kvadraten på det utrymme som används av Turing-maskinen.

---

Följderna

Några viktiga följder av satsen inkluderar:

PSPACE = NPSPACE

Det vill säga de språk som kan kännas igen av deterministiska polynom-rymd Turing-maskiner och icke-deterministiska polynom-rymd Turing-maskiner är samma. Detta följer direkt av att kvadraten på en polynomfunktion fortfarande är en polynomfunktion. Man tror att ett liknande förhållande inte existerar mellan polynomets tidskomplexitetsklasser, P och NP , även om detta fortfarande är en öppen fråga .

NL ⊆ L ²

Det vill säga att alla språk som kan lösas icke-deterministiskt i logaritmiskt utrymme kan lösas deterministiskt i komplexitetsklassen

$${\mathsf {\color {Blå}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right).$$

Detta följer av att STCON är NL-komplett .

Se även

• Immerman–Szelepcsényi teorem

Anteckningar

•    Arora, Sanjeev ; Barak, Boaz (2009), Beräkningskomplexitet. A modern approach , Cambridge University Press , ISBN 978-0-521-42426-4 , Zbl 1193.68112
•   Papadimitriou, Christos (1993), "Avsnitt 7.3: The Reachability Method", Computational Complexity (1:a upplagan), Addison Wesley, s. 149–150, ISBN 0-201-53082-1
• Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences , 4 (2): 177–192, doi : 10.1016/S0022-0000(70)80006-X , hdl : 10338.dmlcz/120475
•   Sipser, Michael (1997), "Avsnitt 8.1: Savitch's Theorem", Introduction to the Theory of Computation , PWS Publishing, s. 279–281 , ISBN 0-534-94728-X

externa länkar

• Lance Fortnow, Grunderna för komplexiteten, Lektion 18: Savitchs sats . Tillträde 09/09/09.
• Richard J. Lipton , Savitchs sats . Ger en historisk redogörelse för hur beviset upptäcktes.