Space

Space Complexity: 

Space Complexity

Motivation: 

Motivation Complexity classes correspond to bounds on resources One such resource is space: the number of tape cells a TM uses when solving a problem

Introduction: 

Introduction Objectives: To define space complexity classes Overview: Space complexity classes Low space classes: L, NL Savitch’s Theorem Immerman’s Theorem TQBF

Space Complexity Classes: 

Space Complexity Classes For any function f:NN, we define: SPACE(f(n))={ L : L is decidable by a deterministic O(f(n)) space TM} NSPACE(f(n))={ L : L is decidable by a non-deterministic O(f(n)) space TM}

Low Space Classes: 

Low Space Classes Definitions (logarithmic space classes): L = SPACE(logn) NL = NSPACE(logn)

Problem!: 

Problem! How can a TM use only logn space if the input itself takes n cells?! !?

3Tape Machines: 

3Tape Machines . . . . . . . . . input work output read-only write-only read/write Only the size of the work tape is counted for complexity purposes

Example: 

Example Question: How much space would a TM that decides {anbn | n>0} require? Note: to count up to n, we need logn bits

Graph Connectivity: 

Graph Connectivity CONN Instance: a directed graph G=(V,E) and two vertices s,tV Problem: To decide if there is a path from s to t in G? An undirected version is also worth considering

Graph Connectivity: 

Graph Connectivity s t

CONN is in NL: 

CONN is in NL Start at s For i = 1, .., |V| { Non-deterministically choose a neighbor and jump to it Accept if you get to t } If you got here – reject! Counting up to |V| requires log|V| space Storing the current position requires log|V| space

Configurations: 

Configurations The content of the work tape The machine’s state The head position on the input tape The head position on the work tape The head position on the output tape Which objects determine the configuration of a TM of the new type? If the TM uses logarithmic space, there are polynomially many configurations

Log-Space Reductions: 

Log-Space Reductions Definition: A is log-space reducible to B, written ALB, if there exists a log space TM M that, given input w, outputs f(w) s.t. wA iff f(w)B the reduction

Do Log-Space Reductions Imply what they should?: 

Do Log-Space Reductions Imply what they should? Suppose A1 ≤L A2 and A2L; how to construct a log space TM which decides A1? Wrong Solution: w f(w) Use the TM for A2 to decide if f(w)A2 Too Large!

Log-Space reductions: 

Log-Space reductions Claim: if A1 ≤L A2 – f is the log-space reduction A2  L – M is a log-space machine for A2 Then, A1 is in L Proof: on input x, in or not-in A1: Simulate M and whenever M reads the ith symbol of its input tape run f on x and wait for the ith bit to be outputted

NL Completeness: 

NL Completeness Definition: A language B is NL-Complete if BNL For every ANL, ALB. If (2) holds, B is NL-hard

Savitch’s Theorem: 

Savitch’s Theorem Theorem: S(n) ≥ log(n) NSPACE(S(n))  SPACE(S(n)2) Proof: First we’ll prove NLSPACE(log2n) then, show this implies the general case

Savitch’s Theorem: 

Savitch’s Theorem Theorem: NSPACE(logn) SPACE(log2n) Proof: First prove CONN is NL-complete (under log-space reductions) Then show an algorithm for CONN that uses log2n space

CONN is NL-Complete: 

CONN is NL-Complete Theorem: CONN is NL-Complete Proof: by the following reduction: L s t “Does M accept x?” “Is there a path from s to t?”

Technicality: 

Technicality Observation: Without loss of generality, we can assume all NTM’s have exactly one accepting configuration.

Configurations Graph: 

Configurations Graph A Computation of a NTM M on an input x can be described by a graph GM,x: s t (u,v)E if M can move from u to v in one step A vertex per configuration the start configuration the accepting configuration

Correctness: 

Correctness Claim: For every non-deterministic log-space Turing machine M and every input x, M accepts x iff there is a path from s to t in GM,x

CONN is NL-Complete: 

CONN is NL-Complete Corollary: CONN is NL-Complete Proof: We’ve shown CONN is in NL. We’ve also presented a reduction from any NL language to CONN which is computable in log space (Why?) 

A Byproduct: 

A Byproduct Claim: NLP Proof: Any NL language is log-space reducible to CONN Thus, any NL language is poly-time reducible to CONN CONN is in P Thus any NL language is in P. 

What Next?: 

What Next? We need to show CONN can be decided by a deterministic TM in O(log2n) space.

The Trick: 

The Trick u v . . . “Is there a path from u to v of length d?” “Is there a vertex z, so there is a path from u to z of size d/2 and one from z to v of size d/2?” d z

Recycling Space: 

Recycling Space The two recursive invocations can use the same space

The Algorithm: 

The Algorithm Boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if d=1 return FALSE for every vertex v { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } }

Example of Savitch’s algorithm: 

Example of Savitch’s algorithm (a,b,c)=Is there a path from a to b, that takes no more than c steps. 3Log2(d) 1 4 3 2 boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } (1,4,3) (1,4,3)(1,2,2) (1,4,3)(1,2,2)TRUE (1,4,3)(2,4,1) (1,4,3)(2,4,1)FALSE (1,4,3)(1,3,2) (1,4,3)(1,3,2)(1,2,1) (1,4,3)(1,3,2)(1,2,1)TRUE (1,4,3)(1,3,2)(2,3,1) (1,4,3)(1,3,2)(2,3,1)TRUE (1,4,3)(1,3,2)TRUE (1,4,3)(3,4,1) (1,4,3)(3,4,1)TRUE (1,4,3) TRUE boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } } boolean PATH(a,b,d) { if there is an edge from a to b then return TRUE else { if (d=1) return FALSE for every vertex v (not a,b) { if PATH(a,v, d/2) and PATH(v,b, d/2) then return TRUE } return FALSE } }

O(log2n) Space DTM: 

O(log2n) Space DTM Claim: There is a deterministic TM which decides CONN in O(log2n) space. Proof: To solve CONN, we invoke PATH(s,t,|V|) The space complexity: S(n)=S(n/2)+O(logn)=O(log2n) 

Conclusion: 

Conclusion Theorem: NSPACE(logn) SPACE(log2n) How about the general case NSPACE(S(n))SPACE(S2(n))?

The Padding ArgumentMotivation: Scaling-Up Complexity Claims: 

The Padding Argument Motivation: Scaling-Up Complexity Claims space + non-determinism We have: space + determinism can be simulated by… We want: space + non-determinism space + determinism can be simulated by…

Formally: 

Formally NSPACE(s1(n))  SPACE(s2(n))  NSPACE(s1(f(n)))  SPACE(s2(f(n))) Claim: For any two space constructible functions s1(n),s2(n)logn, f(n)n: si(n) can be computed with space si(n) simulation overhead E.g NSPACE(n)SPACE(n2)  NSPACE(n2)SPACE(n4)

Idea: 

Idea NTM . . . n space: O(s1(f(n))) . . . . . . . . . . f(n) space: s1(.) in the size of its input DTM space: O(s2(f(n))) 0 0 . . . n

Padding argument: 

Padding argument Let LNPSPACE(s1(f(n))) There is a 3-Tape-NTM ML: babba  Input Work |x| O(s1(f(|x|)))

Padding argument: 

Padding argument Let L’ = { x0f(|x|)-|x| | xL } We’ll show a NTM ML’ which decides L’ in the same number of cells as ML. babba#00000000000000000000000000000000  Input Work f(|x|) O(s1(f(|x|))

Padding argument – ML’: 

Padding argument – ML’ Count backwards the number of 0’s and check there are f(|x|)-|x| such. 2. Run ML on x. babba00000000000000000000000000000000  Input Work f(|x|) O(s1(f(|x|))) In O(log(f(|x|)) space in O(s1(f(|x|))) space

Padding argument: 

Padding argument babba00000000000000000000000000000000  Input Work f(|x|) O(s1(f(|x|))) Total space: O(s1(f(|x|)))

Padding Argument: 

Padding Argument We started with LNSPACE(s1(f(n))) We showed: L’NSPACE(s1(n)) Thus, L’SPACE(s2(n)) Using the DTM for L’ we’ll construct a DTM for L, which will work in O(s2(f(n))) space.

Padding Argument: 

Padding Argument The DTM for L will simulate the DTM for L’ when working on its input concatenated with zeros babba 00000000000000000000000 Input

Padding Argument: 

Padding Argument When the input head leaves the input part, just pretend it encounters 0s. maintaining the simulated position (on the imaginary part of the tape) takes O(log(f(|x|))) space. Thus our machine uses O(s2(f(|x|))) space.  NSPACE(s1(f(n)))SPACE(s2(f(n)))

Savitch: Generalized Version: 

Savitch: Generalized Version Theorem (Savitch): S(n) ≥ log(n) NSPACE(S(n))  SPACE(S(n)2) Proof: We proved NLSPACE(log2n). The theorem follows from the padding argument. 

Corollary: 

Corollary Corollary: PSPACE = NPSPACE Proof: Clearly, PSPACENPSPACE. By Savitch’s theorem, NPSPACEPSPACE. 

Space Vs. Time: 

Space Vs. Time We’ve seen space complexity probably doesn’t resemble time complexity: Non-determinism doesn’t decrease the space complexity drastically (Savitch’s theorem). We’ll next see another difference: Non-deterministic space complexity classes are closed under completion (Immerman’s theorem).

NON-CONN: 

NON-CONN NON-CONN Instance: A directed graph G and two vertices s,tV. Problem: To decide if there is no path from s to t.

NON-CONN: 

NON-CONN Clearly, NON-CONN is coNL-Complete. (Because CONN is NL-Complete. See the coNP lecture) If we’ll show it is also in NL, then NL=coNL. (Again, see the coNP lecture)

An Algorithm for NON-CONN: 

An Algorithm for NON-CONN Count how many vertices are reachable from s. Take out t and count again. Accept if the two numbers are the same. We’ll see a log space algorithm for counting reachability

N.D. Algorithm for reachs(v, l): 

N.D. Algorithm for reachs(v, l) reachs(v, l) 1. length = l; u = s 2. while (length > 0) { 3. if u = v return ‘YES’ 4. else, for all (u’  V) { 5. if (u, u’) E nondeterministic switch: 5.1 u = u’; --length; break 5.2 continue } } 6. return ‘NO’ Takes up logarithmic space This N.D. algorithm might never stop

N.D. Algorithm for CRs: 

N.D. Algorithm for CRs CRs ( d ) 1. count = 0 2. for all uV { 3. countd-1 = 0 4. for all vV { 5. nondeterministic switch: 5.1 if reach(v, d - 1) then ++countd-1 else fail if (v,u)  E then ++count; break 5.2 continue } 6. if countd-1 < CRs (d-1) fail } 7.return count Recursive call! Assume (v,v)  E

N.D. Algorithm for CRs: 

N.D. Algorithm for CRs CRs ( d 1. count = 0 2. for all uV { 3. countd-1 = 0 4. for all vV { 5. nondeterministic switch: 5.1 if reach(v, d - 1) then ++countd-1 else fail if (v,u)  E then ++count; break 5.2 continue } 6. if countd-1 < fail } 7.return count Main Algorithm: CRs C = 1 for d = 1..|V| C = CR(d, C) return C parameter C , C)

Efficiency: 

Efficiency Lemma: The algorithm uses O(log(n)) space. Proof: There is a constant number of variables ( d, count, u, v, countd-1). Each requires O(log(n)) space (range |V|). 

Immerman’s Theorem : 

Immerman’s Theorem Theorem[Immerman/Szelepcsenyi]: NL=coNL Proof: (1) NON-CONN is NL-Complete (2) NON-CONNNL Hence, NL=coNL. 

Corollary: 

Corollary Corollary: s(n)log(n), NSPACE(s(n))=coNSPACE(s(n)) Proof: By a padding argument.

TQBF: 

TQBF We can use the insight of Savich’s proof to show a language which is complete for PSPACE. We present TQBF, which is the quantified version of SAT.

TQBF: 

TQBF Instance: a fully quantified Boolean formula  Problem: to decide if  is true xyz[(xyz)(xy)] Example: a fully quantified Boolean formula Variables` range is {0,1}

TQBF is in PSPACE: 

TQBF is in PSPACE Theorem: TQBFPSPACE Proof: We’ll describe a poly-space algorithm A for evaluating : If  has no quantifiers: evaluate it If =x((x)) call A on (0) and on (1); Accept if both are true. If =x((x)) call A on (0) and on (1); Accept if either is true. in poly time

Algorithm for TQBF: 

Algorithm for TQBF xy[(xy)(xy)] y[(0y)(0y)] y[(1y)(1y)] (00)(00) (01)(01) (11)(11) (10)(10) 1 0 1 1 0 1 1

Efficiency: 

Efficiency Since both recursive calls use the same space, the total space needed is polynomial in the number of variables (the depth of the recursion)  TQBF is polynomial-space decidable 

PSAPCE Completeness: 

PSAPCE Completeness Definition: A language B is PSPACE-Complete if BPSPACE For every APSAPCE, APB. If (2) holds, then B is PSPACE-hard standard Karp reduction

TQBF is PSPACE-Complete: 

TQBF is PSPACE-Complete Theorem: TQBF is PSAPCE-Complete Proof: It remains to show TQBF is PSAPCE-hard: P “Will the poly-space M accept x?” “Is the formula true?” x1x2x3…[…]

TQBF is PSPACE-Hard: 

TQBF is PSPACE-Hard Given a TM M for a language L PSPACE, and an input x, let fM,x(u, v), for any two configurations u and v, be the function evaluating to TRUE iff M on input x moves from configuration u to configuration v fM,x(u, v) is efficiently computable

Formulating Connectivity: 

Formulating Connectivity The following formula, over variables u,vV and path’s length d, is TRUE iff G has a path from u to v of length ≤d (u,v,1)  fM,x(u, v)  u=v (u,v,d)  wxy[((x=uy=w)(x=wy=v))(x,y,d/2)] w is reachable from u in d/2 steps. v is reachable from w in d/2 steps. simulates AND of (u,w,d/2) and (w,v,d/2)

TQBF is PSPACE-Complete: 

TQBF is PSPACE-Complete Claim: TQBF is PSPACE-Complete Proof:   (s,t,|V|) is TRUE iff there is a path from s to t.  is constructible in poly-time. Thus, any PSPACE language is poly-time reducible to TQBF, i.e – TQBF is PSAPCE-hard. Since TQBFPSPACE, it’s PSAPCE-Complete. 

Summary: 

Summary We introduced a new way to classify problems: according to the space needed for their computation. We defined several complexity classes: L, NL, PSPACE. 

Summary: 

Summary Our main results were: Connectivity is NL-Complete TQBF is PSPACE-Complete Savitch’s theorem (NLSPACE(log2)) The padding argument (extending results for space complexity) Immerman’s theorem (NL=coNL)  By reducing decidability to reachability