Space comlexity Flashcards
Define the space complexity model
Let M : haltm
the space complexity of M is measured by a function
F : N –> N
where f(n) returns the maximal number of tape cells used
for an input n
1: define space(f(n))
2: define Nspace(f(n))
1 : { L | L is a language decided by an O(f(n)) space DTM }
2 : { L | L is a language decided by an O(f(n)) space NDTM }
how to solve All NFA
input : A ==> NFA
question : L(A) = Σ* (does there exist a run)
classical solution:
L(A) = Σ* iff ¬L(A) = ∅
∀ f(n) >= n then NPspace (0(f(n))) = Pspace (0(f2(n)))
Nspace = Pspace
can be proved through the yieldability problem
what is psapce completness
B is pspace complete
is B in Pspace
every problem A is Pspace we can
A <=p B
what is savitch theorem
NDTM can simulate DTM in f^2(n)
space(f(n)) ⊆ Nspace(f(n)) , for All n-> R+ | f(n) >= n
By relying on the Yieldability problem :
checking whether c1 yields to c2 in t steps
where c1 : initial state
c2: accept state
let N be a turning machine, deciding a language in space f(n) , m is a middle configuration
CANYIELD= on input c1 ,c2 , t steps
if t == 1 then chacking whether c1 yields to c2
if t2 >1 , let cm of N deciding w in f(n) space
run CANYIELDS(c1 , cm , t/2)
run CANYIELDS(cm, c2 , t/2)
if accept then accept
else reject
M =on Input w
run CANYIELD(c1, c2 , 2^df(n))
D is the number of configuration
prove Savitch theorem
the naive way is to simulate f(n) on each branch and keeping track of branches solving it using yieldability problem C1 is the start config c2 is the accept config is the max number of steps
what is yieldability problem
Given two configs c1 c2 and checking whether C1 can go to c2 in t steps
it operates, such that, it searches for an intermediate config Cm with t/2 step sand checking:
C1 –> Cm in t/2 step
Cm -> Caccept in t/2
space is reused for each
can sat be solved in a linear time
on the Input < Φ >, where Φ is a boolean formula
for each truth assignment to the variables x1…xm
evaluate Φ
if Φ is true accept else, reject
that clearly shows that the SAT problem has linear space since the tap can be reused on each evaluation
CAn ALL nfa be solved on a linear space
N = on the input where M is ALLnfa
put the marker on the initial state of M
repeat 2^q of M where is the number of M’s states
nondeterministically choose input and update
the market position
if at some point the marker lies on the accepted state of M then accept else reject
what is the issue that can arise with CANYIELD of Savitch theorem?
the issue is the fact the f(n) should know the value of f((n), this can be fixed by setting up the value f(n) = 1,2,3,…. for each I
What is the PSACE class
It is the class of languages that are decided by DTM in polynomial space
what is Pspace complete
A problem B is called Pspace complete :
if B is in Psapce
every A ∈ Pspace , A <=p B
why is it important to solve a complete problem
because solving a complete problem allows solving all the problems in the class because a complete problem can be easily reduced to other problems
explain TQBF problem (Turing quantified boolean formula )
TQBF { | Q is a fully quantified boolean formula that can either be true or false }
Example of fully qualified boolean formula:
∀ x ∃y [(X ∨ y )⋀(X ∨ y )]
Show that TQBF ∈ PSPACE-complete
showing that TQBF in pspace is straightforward, we can have the QBF and evaluate each of its variable and then simulate it on the TQBF
Let the following recursive algorithm :
if Ψ start with ∃y :
call TQBf[ [X / true]]
call TQBF [[X/false]]
if the two calls evaluate to true trutne true else false
if Ψ start with ∀ x:
call TQBf[ [X / true]]
call TQBF [[X/false]]
if the two call evaluate to true trutne true else false
if we study the depth of the formula, we can see that at most the space is equal to the number of the variables
Showing : every A ∈ Pspace , reduces to TQBF
for A = Cook-Levin theorem leads to unwanted result since polynomial-time reduction can not produce exponential space result
prove that TQBF is PSpace-hard
Given PspaceTM M and f F N–>N :
Φ m,w is true if w in L(M)
prove that Generalized geography game is pspace complete
Let the following TM:
M: on input where G is a graph and b is a node of the graph
1 - if b has outdegree is 0 then player 1 loses reject
2- remove b from G , G1 is then obtained
3- let b1…..bn nodes that b was connected to
4- run m on
5- if all this accepts then player 2 has a winning strategy, reject else accepts.
space is reused each time so this Tm runs on O(n^2)
define L and NL problem
It is a Turing machine that uses a few memory (log memory) which contained r/w tape and read-only tape which size is log L: is the class of languages that are decided by deterministic turning machine having read-only tape and r/w working tape which size is O(log n) NL: is the class of languages that are decided by a non-deterministic turning machine having read-only tape and r/w working tape which size is O(log n)
prove that the language A= {0k 1k | K in N} is a member of L
solving this problem simply consists of counting the number of 0 in C0 => is a binary counter whose size is log n
C1 => is a binary counter whose size is log n
and overall of 2logn size is obtained
which is O(log n)
prove that the PATH problem is in NL
This problem mainly consists of checking whether exists a path of length n from s to t such that s =|x| x is the number of vertices in the graph
start in S set the counter C =1
non deterministically select the successors s , s'
if s' = t , accept
C =C+1
if C > n then reject
What is the hierarchy theorem?
consists of the idea of giving more time/space allow deciding more problems
define the space construction theorem
for all space construction function, there is exist a language L that is decided in O(f(x)) and not o(f(x))
A function is a function that is at least O(log n ) is called space construction if it maps a binary representation 1^n of f(n) into O(f(n))
