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:NN, 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,tV
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 ALB,
if there exists a log space TM M that, given input w, outputs f(w) s.t.
wA 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 A2L; 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
BNL
For every ANL, ALB. 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 NLSPACE(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: NLP
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 Argument Motivation: 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 LNPSPACE(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| | xL }
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 LNSPACE(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 NLSPACE(log2n). The theorem follows from the padding argument.
Corollary: Corollary Corollary: PSPACE = NPSPACE
Proof:
Clearly, PSPACENPSPACE.
By Savitch’s theorem, NPSPACEPSPACE.
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,tV.
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 uV {
3. countd-1 = 0
4. for all vV {
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 uV {
3. countd-1 = 0
4. for all vV {
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-CONNNL
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 xyz[(xyz)(xy)] Example: a fully quantified Boolean formula Variables` range is {0,1}
TQBF is in PSPACE: TQBF is in PSPACE Theorem: TQBFPSPACE
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 xy[(xy)(xy)] y[(0y)(0y)] y[(1y)(1y)] (00)(00) (01)(01) (11)(11) (10)(10) 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
BPSPACE
For every APSAPCE, APB. 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?” x1x2x3…[…]
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,vV 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) wxy[((x=uy=w)(x=wy=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 TQBFPSPACE, 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 (NLSPACE(log2))
The padding argument (extending results for space complexity)
Immerman’s theorem (NL=coNL) By reducing decidability to reachability