Space comlexity

Question 1

Define the space complexity model

Answer 1

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

Question 2

1: define space(f(n))
2: define Nspace(f(n))

Answer 2

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 }

Question 3

how to solve All NFA
input : A ==> NFA
question : L(A) = Σ* (does there exist a run)

Answer 3

classical solution:

L(A) = Σ* iff ¬L(A) = ∅

Question 4

∀ f(n) >= n then NPspace (0(f(n))) = Pspace (0(f2(n)))

Nspace = Pspace

Answer 4

can be proved through the yieldability problem

Question 5

what is psapce completness

Answer 5

B is pspace complete
is B in Pspace
every problem A is Pspace we can
A <=p B

Question 6

what is savitch theorem

Answer 6

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

Question 7

prove Savitch theorem

Answer 7

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

Question 8

what is yieldability problem

Answer 8

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

Question 9

can sat be solved in a linear time

Answer 9

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

Question 10

CAn ALL nfa be solved on a linear space

Answer 10

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

Question 11

what is the issue that can arise with CANYIELD of Savitch theorem?

Answer 11

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

Question 12

What is the PSACE class

Answer 12

It is the class of languages that are decided by DTM in polynomial space

Question 13

what is Pspace complete

Answer 13

A problem B is called Pspace complete :
if B is in Psapce
every A ∈ Pspace , A <=p B

Question 14

why is it important to solve a complete problem

Answer 14

because solving a complete problem allows solving all the problems in the class because a complete problem can be easily reduced to other problems

Question 15

explain TQBF problem (Turing quantified boolean formula )

Answer 15

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 )]

Question 16

Show that TQBF ∈ PSPACE-complete

Answer 16

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

Question 17

prove that TQBF is PSpace-hard

Answer 17

Given PspaceTM M and f F N–>N :

Φ m,w is true if w in L(M)

Question 18

prove that Generalized geography game is pspace complete

Answer 18

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)

Question 19

define L and NL problem

Answer 19

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)

Question 20

prove that the language A= {0k 1k | K in N} is a member of L

Answer 20

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)

Question 21

prove that the PATH problem is in NL

Answer 21

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

Question 22

What is the hierarchy theorem?

Answer 22

consists of the idea of giving more time/space allow deciding more problems

Question 23

define the space construction theorem

Answer 23

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))